%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% Last Modified by Suri on 19-Sept-2010 %%%%%%%%%
%%%%%%% Last Modified by Suri on 01-October-2010 %%%%%%%%
%%%%%%% Last Modified by Suri on 11-October-2010 %%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% This is "aamas2010_cameraReady.tex" Dec 2010
% This file should be compiled with "aamas2010.cls" July 2010 or "aamas2010_extendedAbstract.cls" Dec 2010
%
% This example file demonstrates the use of the 'aamas2010.cls'
% LaTeX2e document class file. It is for those submitting
% articles to AAMAS 2010 conference. This file is based on
% the sig-alternate.tex example file.
% The 'sig-alternate.cls' file of ACM will produce a similar-looking,
% albeit, 'tighter' paper resulting in, invariably, fewer pages.
% than the original style ACM style.
%
% ----------------------------------------------------------------------------------------------------------------
% This .tex file (and associated .cls ) produces:
%       1) The Permission Statement
%       2) The Conference (location) Info information
%       3) The Copyright Line with AAMAS data
%       4) NO page numbers
%
% as against the acm_proc_article-sp.cls file which
% DOES NOT produce 1) thru' 3) above.
%
% Using 'aamas2010.cls' you don't have control
% from within the source .tex file, over both the CopyrightYear
% (defaulted to 200X) and the IFAAMAS Copyright Data
% (defaulted to X-XXXXX-XX-X/XX/XX).
% These information will be overwritten by fixed AAMAS 2010 information
% in the style files - it is NOT as you are used with ACM style files.
%
% ---------------------------------------------------------------------------------------------------------------
% This .tex source is an example which *does* use
% the .bib file (from which the .bbl file % is produced).
% REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission, you *NEED* to 'insert'
% your .bbl file into your source .tex file so as to provide
% ONE 'self-contained' source file.
%

% This is the document class for full camera ready papers and extended abstracts repsectively

\documentclass{aamas2010_cameraReady}
%\documentclass{aamas2010_extendedAbstract}

% if you are using PDF LaTex and you cannot find a way for producing
% letter, the following explicit settings may help

\pdfpagewidth=8.5truein \pdfpageheight=11truein

\usepackage{multirow}

%\usepackage[T1]{fontenc}
%\usepackage[latin9]{inputenc}
%\usepackage{amsthm}
%\usepackage{amsmath}
%\usepackage{graphicx}

\numberwithin{equation}{section} \numberwithin{figure}{section}
%\theoremstyle{plain}
\newtheorem{thm}{Theorem}
 % \theoremstyle{plain}
  \newtheorem{lem}[thm]{Lemma}
 % \theoremstyle{plain}
  \newtheorem{cor}[thm]{Corollary}

\newcommand{\N}{\mbox{\bbb N}}

\newtheorem{theorem}{\bf Theorem}
\newtheorem{lemma}{\bf Lemma}
\newtheorem{definition}{\bf Definition}
\newtheorem{example}{\bf Example}
\newtheorem{conjecture}{\bf Conjecture}

\begin{document}

% In the original styles from ACM, you would have needed to
% add meta-info here. This is not necessary for AAMAS 2010 as
% the complete copyright information is generated by the cls-files.

% For appropriate information about authors and title written in the
% copyright information, you must use these commands. Note that the copyright
% box is not required for the initial submission.

\AuthorsForCitationInfo{Author1, Author2 and Author3}

\TitleForCitationInfo{The title of your paper should be written
here}

\title{The Price of Stability in Networks Formed with Only Local Information}

% AUTHORS


% For initial submission, do not give author names, but the
% tracking number, instead, as the review process is blind.

% You need the command \numberofauthors to handle the 'placement
% and alignment' of the authors beneath the title.
%
% For aesthetic reasons, we recommend 'three authors at a time'
% i.e. three 'name/affiliation blocks' be placed beneath the title.
%
% NOTE: You are NOT restricted in how many 'rows' of
% "name/affiliations" may appear. We just ask that you restrict
% the number of 'columns' to three.
%
% Because of the available 'opening page real-estate'
% we ask you to refrain from putting more than six authors
% (two rows with three columns) beneath the article title.
% More than six makes the first-page appear very cluttered indeed.
%
% Use the \alignauthor commands to handle the names
% and affiliations for an 'aesthetic maximum' of six authors.
% Add names, affiliations, addresses for
% the seventh etc. author(s) as the argument for the
% \additionalauthors command.
% These 'additional authors' will be output/set for you
% without further effort on your part as the last section in
% the body of your article BEFORE References or any Appendices.

%\numberofauthors{8} %  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.
%

\numberofauthors{3}

%\author{
% You can go ahead and credit any number of authors here,
% e.g. one 'row of three' or two rows (consisting of one row of three
% and a second row of one, two or three).
%
% The command \alignauthor (no curly braces needed) should
% precede each author name, affiliation/snail-mail address and
% e-mail address. Additionally, tag each line of
% affiliation/address with \affaddr, and tag the
% e-mail address with \email.
% 1st. author

%\alignauthor
%Ben Trovato\titlenote{Dr.~Trovato insisted his name be first.}\\
%       \affaddr{Institute for Clarity in Documentation}\\
%       \affaddr{1932 Wallamaloo Lane}\\
%       \affaddr{Wallamaloo, New Zealand}\\
%       \email{trovato@corporation.com}
%% 2nd. author
%\alignauthor
%G.K.M. Tobin\titlenote{The secretary disavows any knowledge of this author's actions.}\\
%       \affaddr{Institute for Clarity in Documentation}\\
%       \affaddr{P.O. Box 1212}\\
%       \affaddr{Dublin, Ohio 43017-6221}\\
%       \email{webmaster@marysville-ohio.com}
%% 3rd. author
%\alignauthor Lars Th{\o}rv{\"a}ld\titlenote{This author is the one who did all the really hard work.}\\
%       \affaddr{The Th{\o}rv{\"a}ld Group}\\
%       \affaddr{1 Th{\o}rv{\"a}ld Circle}\\
%       \affaddr{Hekla, Iceland}\\
%       \email{larst@affiliation.org}
%}

%\and  % use '\and' if you need 'another row' of author names

% 4th. author
%\alignauthor Lawrence P. Leipuner\\
%       \affaddr{Brookhaven Laboratories}\\
%       \affaddr{Brookhaven National Lab}\\
%       \affaddr{P.O. Box 5000}\\
%       \email{lleipuner@researchlabs.org}

% 5th. author
%\alignauthor Sean Fogarty\\
%       \affaddr{NASA Ames Research Center}\\
%       \affaddr{Moffett Field}\\
%       \affaddr{California 94035}\\
%       \email{fogartys@amesres.org}

% 6th. author
%\alignauthor Charles Palmer\\
%       \affaddr{Palmer Research Laboratories}\\
%      \affaddr{8600 Datapoint Drive}\\
%       \affaddr{San Antonio, Texas 78229}\\
%       \email{cpalmer@prl.com}

%\and

%% 7th. author
%\alignauthor Lawrence P. Leipuner\\
%       \affaddr{Brookhaven Laboratories}\\
%       \affaddr{Brookhaven National Lab}\\
%       \affaddr{P.O. Box 5000}\\
%       \email{lleipuner@researchlabs.org}

%% 8th. author
%\alignauthor Sean Fogarty\\
%       \affaddr{NASA Ames Research Center}\\
%       \affaddr{Moffett Field}\\
%       \affaddr{California 94035}\\
%       \email{fogartys@amesres.org}

%% 9th. author
%\alignauthor Charles Palmer\\
%       \affaddr{Palmer Research Laboratories}\\
%       \affaddr{8600 Datapoint Drive}\\
%       \affaddr{San Antonio, Texas 78229}\\
%       \email{cpalmer@prl.com}

%}

%% There's nothing stopping you putting the seventh, eighth, etc.
%% author on the opening page (as the 'third row') but we ask,
%% for aesthetic reasons that you place these 'additional authors'
%% in the \additional authors block, viz.
%\additionalauthors{Additional authors: John Smith (The Th{\o}rv{\"a}ld Group,
%email: {\texttt{jsmith@affiliation.org}}) and Julius P.~Kumquat
%(The Kumquat Consortium, email: {\texttt{jpkumquat@consortium.net}}).}
%\date{30 July 1999}
%% Just remember to make sure that the TOTAL number of authors
%% is the number that will appear on the first page PLUS the
%% number that will appear in the \additionalauthors section.

\maketitle

\begin{abstract}
Consider a set of strategic agents who wish to form links among
themselves for the purpose of ensuing traffic or information.
Being rational and intelligent, agents form or delete links with
other agents to maximize their respective utilities. In this
paper, we analyze network formation in such scenarios by focusing
on a network formation game with local information (NFGL) wherein
the agents are the players and the utility of each agent depends
only on its immediate neighborhood in the network (we refer to
this as local information). In such decentralized scenarios, in
general, the set of equilibrium network topologies may be quite
different from the topologies of centrally enforced optimum (or
efficient) networks. There are two parameters in the proposed
model: benefit $\delta \in (0,1)$ from each immediate neighbor and
cost $c > 0$ of maintaining a link. In this setting, we study the
tradeoffs between topologies of equilibrium networks and efficient
networks. Using the proposed NFGL, we characterize topologies of
equilibrium networks and topologies of efficient networks by
drawing upon classical results from extremal graph theory. Then we
study the price of stability (ratio of the sum of utilities of
agents in a best equilibrium network to that of an efficient
network) in NFGL. Interestingly, we find that price of stability
is $1$ for almost all configurations of $\delta$ and $c$. For the
remaining configurations of $\delta$ and $c$, we obtain a lower
bound of 0.5 on price of stability. This indicates that, under
mild conditions, efficient networks will form when strategic
agents choose to add and/or delete links based on only local
information. This is desirable from system design view point.



%Consider a set of rational and intelligent agents who wish to form
%links among themselves for the purpose of routing information or
%traffic. Being rational and intelligent, agents form links with
%other agents so that their respective utilities are maximized. In
%such scenarios, in general, the set of equilibrium network
%topologies may appear quite different from the topologies of
%centrally enforced optimum (or efficient) networks. In this paper,
%we focus on a {\em local network formation game (LNFG)} wherein
%the agents are the players and the utility of each agent depends
%only on the local information in the network (or the neighborhood
%of the agent). In this setting, we study the tradeoffs between
%topologies of equilibrium networks and efficient networks. Perhaps
%this is the first effort to study the compatibility of equilibrium
%versus efficiency in the process of network formation with only
%local information. Towards this end, using the proposed LNFG, we
%characterize topologies of equilibrium networks and
%topologies of efficient networks based on a few classical results
%from extremal graph theory. Then we study the price of stability
%(ratio of the sum of utilities of agents in a best equilibrium
%network to that of an efficient network) in LNFG in order to
%reveal the compatibility of equilibrium networks versus
%efficient networks. Interestingly, we find that price of stability
%is $1$ for almost all values of the parameters in LNFG. Only for a
%few values of the parameters in LNFG, we obtain a lower bound of
%$\frac{1}{2}$ on price of stability. This indicates that, under
%mild conditions, the proposed LNFG produces equilibrium networks
%that are efficient as well. Moreover, we have experimentally
%studied the dynamics of LNFG and, in this process, we also
%validated the analytical predictions of the topologies of
%equilibrium networks using LNFG.
\end{abstract}

% Note that the category section should be completed after reference to the ACM Computing Classification Scheme available at
% http://www.acm.org/about/class/1998/.
\vspace{-0.1in}
%\category{H.4}{Information Systems Applications}{Miscellaneous}
\category{G.2.2}{Mathematics of
Computing}{DiscreteMathematics}[graph theory, network problems]
\category{I.2.11}{Computing Methodologies}{Artificial
Intelligence}[distributed artificial intelligence]


%A category including the fourth, optional field follows...
%\category{D.2.8}{Software Engineering}{Metrics}[complexity measures, performance measures]

%General terms should be selected from the following 16 terms: Algorithms, Management, Measurement, Documentation, Performance, Design, Economics, Reliability, Experimentation, Security, Human Factors, Standardization, Languages, Theory, Legal Aspects, Verification.

\terms{Economics, Design}

%Keywords are your own choice of terms you would like the paper to be indexed by.

\keywords{Network formation, rationality, agents, pairwise
stability, efficiency, price of stability.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Introduction %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vspace{-0.07in}
\section{Introduction}
\label{introduction}

In many network settings, the behavior of the system is driven by
the actions of a large number of autonomous agents, each motivated
by self-interest and optimizing an individual objective function.
As a consequence of this, the global performance of such networks,
which are the equilibrium outcomes of decentralized strategic
interactions, can be worse than that of a network that is enforced
by a central authority. In the literature, networks that are
enforced by a central authority are known as efficient networks.
Understanding the compatibility between the equilibrium networks
and efficient networks is the primary focus of research in network
formation \cite{jackson:08, goyal:07, hummon00, doreian06,
corbo:05, galeotti:06, jackson:02}.

The crux of most of the models for network formation in the
literature \cite{jackson-wolinsky:96, anshelevich:03, anshelevich:08, 
fabrikant:03, corbo:05, galeotti:06} is the underlying
strategic form game where the players, strategies, and utilities are defined as follows: (i) the
individual agents are the players, (ii) the strategy of each agent
is a subset of other agents with which it wants to form links, and
(iii) the utility of each agent depends on the structure of the
network.
%By employing various notions of equilibrium and
%efficiency, the above studies in the literature yield precise
%predictions on the topologies of equilibrium and efficient
%networks.

Another key aspect of most of the existing work in the literature
is that they model the process of network formation in a decentralized fashion,
in the sense that the agents in the network take autonomous
decisions whether to form or delete links with other agents.
However, these models require the agents to know the global
structure of the network to compute their respective utilities.
This is a demanding requirement as, in several real life
decentralized applications, it is unlikely that any individual
agent knows the global structure of the network.  For example, in
friendship networks, an individual more often does not even know
who are all the friends of his friends. Thus, it is very important
to study the process of network formation where each individual
agent knows only its immediate neighborhood. In the rest of the
paper, we refer to this setting as {\em network formation with
only local information}. The primary contribution of this work is to 
model the process of network formation with only local information, and
study the compatibility between equilibrium networks and efficient 
networks in such a context.
% We attempt to address this research gap and, in this sense, this
% paper contributes to the growing literature on network formation.

%We note that our proposed model is more close to real life
%settings than many models in the literature, as often an
%individual agent does not even know who are all the neighbors of
%its neighbors in the network.
We note that our model assumes that a link forms with the consent
of both the agents (refer to Section \ref{utilitymodel}), as more
often social contacts emerge in this manner. In such situations,
an appropriate choice for the notion of equilibrium is pairwise
stability \cite{jackson-wolinsky:96}. Informally, we call a
network pairwise stable if no agent can improve its utility by
deleting any link and no two unconnected agents can form a link to
improve their respective utilities. We call a network efficient if
the sum of utilities of the agents is maximal. In this framework,
our objective is to investigate the tradeoffs between topologies
of pairwise stable and efficient networks. In the rest of the 
paper, we use the terms {\em graph\/} and {\em network\/} 
interchangeably.


%In this paper, we focus on network formation games with local
%information wherein the utility of each agent depends only the
%structure of its neighborhood. This certainly reduces the burden
%on the agents in the sense that agents individually need not know
%the entire network structure to maximize their respective
%utilities. In fact, in several real-life applications, agents form
%or delete links with others without knowing the entire network
%structure. For example, (a) In buyer-seller networks, the agents
%(buyers or sellers) actually do not know the structure of the
%entire trading network; and (b) In practice, an individual in a
%online social network (such as Orkut, Facebook, LinkedIn, etc.)
%does not even know who are all the friends of his/her friend. Thus
%it is very important to study network formation with only
%local information. We note that there is not much work in the
%literature towards this end (please refer to relevant work for
%more details).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Relevant Work %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Relevant Work}
\label{relevant-work}

% There are many possible approaches to modeling network formation.
%The initial efforts in this line of research dates back to the
%seminal works of Aumann and Myerson \cite{aumann:88} and Myerson
%\cite{myerson:91}. Though these models are simple to analyze and
%captures several aspects of network formation, they generally
%possess a large multiplicity of Nash equilibria \cite{jackson:04,
%jackson:08}.

% Due to the simplicity of the strategic form game model proposed by
% Myerson \cite{myerson:91}, it has become a popular approach to
% model network formation in the literature \cite{jackson:08,
% goyal:07, hummon00, doreian06, buskens-vanderijt:07,
% goyal-vegaredondo:07, kstw:08, arcaute:08, anshelevich:03,
% leonardi:07, anshelevich:08, fabrikant:03, corbo:05, galeotti:06,
% jackson-wolinsky:96, jackson:02} and the references in these
% papers. 

The modeling of strategic network formation in a general setting
was first studied in Jackson and Wolinsky
\cite{jackson-wolinsky:96}. The authors defined a notion of
equilibrium called {\em pairwise stability } and 
study the tension between efficiency and pairwise stability by deriving
various conditions under which efficiency and pairwise stability are compatible.
%An important feature their model does not capture is
%that of the intermediary benefits that nodes gain by being
%intermediaries lying on the paths between non-neighbor nodes. In
%particular, they do not capture the benefits due to structural
%holes.
Using agent-based simulation approaches, Hummon \cite{hummon00}
and Doreian \cite{doreian06} identified certain pairwise stable
structures that are more specific than those anticipated by the
analytical findings of \cite{jackson-wolinsky:96}.
%More recently, \cite{doreian08a} investigated this phenomenon in a
%broader context and later \cite{doreian08b} presented some
%specific results for the context of structural holes.

Fabrikant \cite{fabrikant:03} studied a network creation game in
the context of communication networks where links are generated by
the unilateral actions of players and link costs are one-sided.
The utility of each agent is the sum of the cost to form links and
the distances to the rest of agents in the network. Corbo and
Parkes \cite{corbo:05} extended this model to the context of
bilateral network formation where the consent of both the agents
is required to form a link. The authors \cite{corbo:05} also study
the price of anarchy of the bilateral network formation game and
they show that the worst-case price of anarchy of the bilateral
model is worse than for the unilateral model \cite{fabrikant:03}.

Anshelevich \cite{anshelevich:03,anshelevich:08} studied a
cost-sharing network connection game where, given an undirected
graph $G$, players have a set of specified terminal nodes that
they wish to be connected in the purchased network (which is
necessarily a subgraph of $G$). In \cite{anshelevich:08}, the
authors studied how fair cost allocation schemes affect the
quality of the best Nash equilibrium network.

Goyal and Vega-Redondo \cite{goyal-vegaredondo:07} proposed a
non-cooperative game model wherein they capture the bridging
benefits that nodes can gain by occupying structural positions. In
this setting, the authors studied the tradeoffs between stability
and efficiency.

The following limitation is common to all the previous models in
the literature: each agent needs to know global information about
the structure of the network in order to maximize its utility.

We note that there are three models \cite{buskens-vanderijt:07,
arcaute:08, kstw:08} in the literature that are close to our
proposed model. The model \cite{buskens-vanderijt:07} requires
each individual agent to know just its immediate neighbors (or
$1$-hop neighborhood) to optimize its own utility. The authors
conducted a systematic analysis of tradeoffs between equilibrium
and efficiency. However, the model \cite{buskens-vanderijt:07}
captures only the cost to nodes, and it ignores various benefits
that nodes can derive from the network such as direct benefits
from the neighbors and the bridging benefits.

The authors \cite{arcaute:08} studied the myopic dynamics in
network formation games. A key property of the dynamics studied in
this model \cite{arcaute:08} is that they are local and the
authors showed that these dynamics converge to efficient or near
efficient outcomes. However, the model \cite{arcaute:08} does not
characterize the topologies of equilibrium and efficient networks.
Moreover, the model \cite{arcaute:08} works with Pareto efficiency
and we work with a different notion of efficiency (as mentioned in
the introduction).

The main focus of the model \cite{kstw:08} was to characterize the
structure of stable networks with {\em Nash equilibrium\/} as the
notion of stability. The authors proposed a polynomial time
algorithm for a node to determine its best response in a given
graph as nodes can choose to link to any subset of other nodes.
They also showed that stable networks have a rich combinatorial
structure. However, the model \cite{kstw:08} needs each individual
agent to know its $2$-hop neighborhood (the set of all individuals
that are reachable within two hops) to optimize its own utility.
The model \cite{kstw:08} works with Nash equilibrium and our
proposed model works with pairwise stability as the notion of
equilibrium. Moreover, the model \cite{kstw:08} does not study the
tradeoffs between the topologies of stable networks and the
topologies of efficient networks.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Our Results %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Our Contributions}
\label{results}

%From the above discussion on the existing models for network
%formation in the literature, all the models are decentralized in
%the sense that individuals in the network take autonomous
%decisions whether to form/delete links with other individuals.
%However, these models require that each individual should know the
%entire network structure in order to optimize his/her own utility.
%This is very a demanding requirement as, in real life
%applications, it is unlikely that any individual knows the entire
%network structure. For example, in online social communities such
%as LinkedIn, Orkut, Facebook, almost surely nobody in the network
%knows the network structure. A first step towards this line of
%research is the model proposed by Kleinberg et. al. \cite{kstw:08}
%and here each individual should know about its $2$-hop
%neighborhood in order to maximize his/her utility. The model
%\cite{kstw:08} assumes that links form unilaterally and considers
%Nash equilibrium as the notion of stability. However, the authors
%\cite{kstw:08} do not study the compatibility of stability and
%efficiency.
%
%In this paper, we propose a strategic form game model for network
%formation where each individual should know only its neighborhood
%in order maximize his/her utility. From now on, we refer this
%setting as {\em network formation with local information}. Our
%proposed model is more close to real life applications than the
%model \cite{kstw:08}, as often we do not know who are the
%neighbors of our neighbors (for example, we do not even know who
%are all the friends of our friends in online social communities).
%Moreover, our model assumes that any link forms with the consent
%of both the individuals, as it is the typical nature of social
%contacts. In such situations, an intuitive choice of the notion of
%stability is pairwise stability \cite{jackson-wolinsky:96}. To the
%best of our knowledge, this is perhaps the first effort to study
%the compatibility of pairwise stable networks versus efficient
%networks in the context of network formation with local
%information.


%The following are the main contributions of this paper:
%\begin{itemize}
%\item We first propose a non-cooperative game (LNFG) to model
%network formation with local information. This model assumes that
%any link forms with the consent of both the individuals. The
%utility of each agent in LNFG depends on the following facts: (a)
%the benefits and the costs associated with the links to immediate
%neighbors; and (b) the benefits that arise from bridging pairs of
%non-neighbor nodes. In other words, the utility of each node just
%depends on its neighborhood.
%
%\item In this setting, we characterize the topologies of pairwise
%stable networks. In particular, we show that the cycle network and
%the complete bi-partite network are the non-empty pairwise stable
%networks. We note that our findings extend the possible topologies
%for pairwise stable networks compared to that of other models in
%the literature.
%
%\item We then characterize the topologies of efficient networks
%with respect to the LNFG. We do this using a few classical
%results from extremal graph theory. We show that the complete network
%and the Turan network are the only non-empty efficient networks under
%appropriate conditions.
%
%\item Next, we study the price of stability (PoS) of LNFG. We show
%that PoS is $1$ for many configurations of the parameters and, for
%the rest, we show a lower bound of $\frac{1}{2}$ for Pos. This
%indicates that, under mild conditions, the proposed LNFG produces
%equilibrium networks that are efficient as well.
%
%\item Moreover, we have experimentally studied the dynamics of
%LNFG and, in this process, we also validated the analytical
%predictions of the topologies of equilibrium networks using LNFG.
%\end{itemize}

The following are our specific contributions.
\begin {itemize}
\item We propose a strategic form game to model the process of 
network formation with only local information and we term the game as {\em network formation game with
local information} (NFGL). The game has $n$ players and the utility of each player takes into account not
only the benefits ($\delta \in (0,1)$) that arise from routing information to and from its neighbors but also the cost ($c > 0$)
to maintain a link to each of its neighbors.

\item We understand the pairwise stability properties of NFGL by 
characterizing topologies of the pairwise stable networks. 
%We note that our findings extend the possible topologies for
%pairwise stable networks compared to that of other models in the
%literature.
Next, we simulate dynamics of NFGL to understand the 
how pairwise-stable networks evolve overtime. We present simulation results based on NFGL
and these results validate our analytical predictions of the topologies of pairwise stable networks.

\item We then analytically predict topologies of efficient networks by drawing upon classical results from extremal
graph theory.

\item Using the above derived results, we study the price of stability (PoS) (\cite{anshelevich:08}) in NFGL
to reveal the tradeoffs between pairwise stable networks and the efficient networks. The PoS is the ratio of
the sum of utilities of the players in a best pairwise stable network to that of an efficient network. Here a best pairwise
stable network means a pairwise stable network with a maximum value of sum of utilities of the players. Interestingly, we find
that PoS is $1$ for almost all configurations of $\delta$ and $c$. For the remaining configurations of $\delta$ and $c$, we obtain a
lower bound of $\frac{1}{2}$ on PoS. This implies that, under mild conditions, the proposed NFGL produces pairwise stable networks
that are efficient.

\item We finally summarize and discuss possible avenues for future work in Section \ref{conclusion}.
\end {itemize}

\subsection{Outline of The Paper}
\label{out-line}
The rest of the paper is organized as follows. In \text{Section~\ref{utilitymodel}}, 
we first present the NFGL in formal terms and explain the various components of the game in detail. 
In \text{Section~\ref{sec:Stability}}, we characterize the structure of \textit{pairwise-stable} 
networks in NFGL and present few important results in this regard. \text{Section~\ref{sec:Simulations}} 
examines pairwise-stability in more detail by studying the dynamic process of network formation in NFGL 
by performing simulations using a custom-built social network simulator that models the NFGL. 
In Section~\ref{sec:Efficiency}, we explore the subject of efficiency in NFGL and present some 
interesting results under various cost-benefit parameters. Using the results of Section~\ref{sec:Stability} 
and Section~\ref{sec:Efficiency}, we evaluate the price of stability values of the NFGL in Section~\ref{POS}. 
We finally summarize and discuss possible avenues of future work in Section~\ref{conclusion}. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LNFG %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{The Model}
\label{utilitymodel}

We model network formation with only local information using a
strategic form game \cite{myerson:91}. We consider a network setup with 
$n$ players denoted by $N=\{1,2,\ldots, n\}$. $|N|$ denotes the cardinality of set $N$. 
A strategy $s_i$ of a player $i$ is any subset of players with which
the player would like to establish links. We assume that the
formation of a link requires the consent of both the players.
Assume that $S_i$ is the set of strategies of player $i$. Let
$s=(s_1, s_2, \ldots, s_n)$ be a profile of strategies of the
players. Also let $S$ be the set of all such strategy profiles.
Each strategy profile $s$ leads to an undirected graph and we
represent it by $G(s)$. If there is no confusion, we just use $G$.
%Let $\Psi(S)$ be the set of all such undirected graphs. When the
%context is clear, we use $g$ and $\Psi$ instead of $g(s)$ and
%$\Psi(S)$ respectively.
%If the strategy profile $s$ is clear from the context, we simply
%the denote the corresponding graph by $g$ rather than $g(s)$.
%If players $i$ and $j$ are connected by a link in a graph $g$,
%then we say that $(i,j) \in g$, otherwise we say that $(i,j)
%\notin g$.
If players $x$ and $y$ form a link $(x,y)$ in a graph $g$, then we
represent the new graph by $g + (x,y)$. We assume that players in
the network communicate using shortest paths - this is a standard
assumption used in the literature for ease of modeling. In the
rest the paper, we use the terms players, nodes, and agents
interchangeably.

{\em Degree of Node:} Let $d_{i}$ be the degree of node $i$ in a
given undirected graph. $d_i$ represents the number of neighbors
of node $i$.

{\em Costs:} If nodes $i$ and $j$ are connected by a link, then we
assume that the link incurs a cost $c > 0$ to each node. That is,
if the degree of node $i$ is $d_i$, then node $i$ incurs a cost of
$cd_i$.

{\em Benefits from Immediate Neighbors:} Assume that $\delta \in
(0,1)$. If nodes $i$ and $j$ are connected by a link, then we
assume that node $i$ and node $j$ gain a benefit of $\delta$ each.
That is, if the degree of node $i$ is $d_i$, then node $i$ gains a
benefit of $\delta d_i$ from its immediate neighbors.

{\em Bridging Benefits:} If two non-neighbor nodes $j$ and $k$
have a shortest path through node $i$; and nodes $j$ and $k$
communicate using this path, then (i) we assume that a benefit of
$\delta^{2}$ arises due to this communication, and (ii) we also
assume that the benefit $\delta^{2}$ entirely goes to node $i$. We
refer to $\delta^{2}$ as the bridging benefit to node $i$. The
main motivation for this kind of bridging benefits is by
sociological studies suggesting that in practice most of the
bridging benefits arise from bridging the communication between
pairs of non-neighbor nodes in the network \cite{burt:07}.

In this framework, we define the utility of agent $i$ such that it
depends on the benefits from immediate neighbors, the costs to
maintain links to these immediate neighbors, and the bridging
benefits. More formally, for any $i \in N$, the utility $u_i$ of
agent $i$ in an undirected graph $G$ is defined as follows:
\begin{equation}
u_i(G) = d_i(\delta - c) + d_i \Biggl(1-\frac{\sigma_i}{{d_i
\choose 2}}\Biggr) \delta^2
\end{equation}
where $\sigma_i$ is the number of links among the neighbors of
node $i$ in $G$. There are two terms in this utility function. The
first term specifies the net benefit to node $i$ from its
immediate neighbors. The second term specifies the sum of bridging
benefits to node $i$. Here $1-\frac{\sigma_i}{{d_i \choose 2}}$ is
the fraction of pairs of neighbors of node $i$ that are
non-neighbors and $d_i$ normalizes the level of bridging benefits
that node $i$ gains in the network. For example, the fraction of
pairs of neighbors of node $1$ that are non-neighbors in both $g1$
and $g3$ in Figure \ref{model-illustration} is $1.0$. However the
degree of node $1$ in $g1$ is $d_1 = 5$ and the degree of node $1$
in $g3$ is $d_1 = 2$. The normalization term $d_i$ ensures that the
bridging beneifit for node $1$ is higher in $g1$ than in $g3$.

{\em Note: Assume that node $i$ bridges the communication between
$j$ and $k$; and a benefit of $\delta^{2}$ is generated. In the
literature, there are three well known ways of distributing the
benefit $\delta^{2}$ to nodes $i$, $j$, and $k$: (i) only node $i$
gets entire $\delta^{2}$, (ii) node $i$ gets $0$, and (iii) nodes
$i$, $j$, and $k$ get equal share of $\delta^{2}$. In this paper,
we work with scenario (i). A similar approach is utilized in
\cite{kstw:08} as well. We note that the analysis that we perform
using scenario (i) can be easily extended to other two scenarios.}

\subsection{The Strategic Form Game}
The above framework defines a strategic form game $\Gamma =
\Bigl(N, (S_i)_{i \in N}, (u_i)_{i \in N} \Bigr)$ that models
network formation with local information. We refer to this as
network formation game with local information (NFGL). The
following example illustrates NFGL.
\vspace{-0.05in}
\begin{example}
\label{nfgl-illustration}
Assume that $N=\{1,2,3,4,5,6\}$ is the
set of $6$ players. If $s_1 = \{2,3,4,5,6\}$, $s_2 = \{1\}$, $s_3
= \{1\}$, $s_4 = \{1\}$, $s_5 = \{1\}$, $s_6 = \{1\}$, then the
resultant graph $g1$ is the star graph as shown in Figure
\ref{model-illustration}.(i). Note that an edge forms with the
consent of both the nodes.
\vspace{-0.15in}
\begin{figure}[!hbtp]
\begin{center}
\includegraphics[scale=0.357]{model-illustration.jpg}
\end{center}
\vspace{-0.2in} \caption{An illustrative example
\label{model-illustration}}
\end{figure}
\vspace{-0.1in}
The utilities of the players in the star graph are as follows:
$u_1(g1)=5(\delta-c) + 5\delta^{2}$ and $u_2(g1) = u_3(g1) =
u_4(g1) = u_5(g1) = u_6(g1) = (\delta-c)$.

If $s_1 = \{2,3,4,5,6\}$, $s_2 = \{1,3,6\}$, $s_3 = \{1,2,4\}$,
$s_4 = \{1,3,5\}$, $s_5 = \{1,4,6\}$, $s_6 = \{1,2,5\}$, then the
resultant graph $g2$ is the wheel graph as shown in Figure
\ref{model-illustration}.(ii). The utilities of the players in the
wheel graph are as follows: $u_1(g2)=5(\delta-c) +
\frac{5\delta^{2}}{2}$ and $u_2(g2) = u_3(g2) = u_4(g2) = u_5(g2)
= u_6(g2) = 3(\delta-c) + \delta^{2}$.

On similar lines, if $s_1 = \{2,6\}$, $s_2 = \{1,3\}$, $s_3 =
\{2,4\}$, $s_4 = \{3,5\}$, $s_5 = \{4,6\}$, $s_6 = \{1,5\}$, then
the resultant graph $g3$ is the cycle (shared) graph as shown in
Figure \ref{model-illustration}.(iii). The utilities of the
players in the cycle graph are as follows: $u_1(g3) = u_2(g3) =
u_3(g3) = u_4(g3) = u_5(g3) = u_6(g3) = 2(\delta-c) +
2\delta^{2}$.
\end{example}


\section{Structure of Pairwise Stable \\Networks}\label{sec:Stability}

In this section, we first recall the notion of pairwise stability.
Then, we characterize the topologies of pairwise stable networks.
To begin with, we note that the notion of pairwise stability is
defined in Jackson-Wolinsky~\cite{jackson-wolinsky:96}. Formally,
we call an undirected graph \text{$G=(V,E)$} pairwise
stable~\cite{jackson-wolinsky:96} if (i) $\forall (i,j) \in E,
u_i(G) \geq u_i(G-(i,j))$ and $\text{$u_j(G) \geq u_j(G-(i,j))$}$,
(ii) $\forall (i,j) \notin E$, if $u_i(G) < u_i(G+(i,j))$ then
$u_j(G) > u_j(G+(i,j))$.

We now focus on characterizing the topologies of the pairwise
stable networks that may emerge following the framework in NFGL.

% We start with an initial configuration of the network. The
% structure of the network changes over time as various agents in
% the network add and/or remove links with other agents, so as to
% maximize their respective utilities. It would be interesting to
% determine if, in the long run, the network reaches a pairwise
% stable state. If the network does reach a pairwise stable state,
% it would be interesting to know the topology of that network. One
% approach is to analytically study the asymptotic network structure
% in the limit as time tends to infinity. However, the dynamics of
% the system can become very complex even in a moderately sized
% network, making such an approach infeasible
% \cite{doreian06,hummon00}. Moreover, such an approach is very
% sensitive to the initial configuration of the network.

Characterizing pairwise stable networks has been addressed in the
literature by well known works like \cite{jackson:08},
\cite{goyal:07}, \cite{buskens-vanderijt:07},
\cite{goyal-vegaredondo:07}, \cite{kstw:08}, \cite{fabrikant:03},
\cite{corbo:05}, \cite{galeotti:06}, \cite{jackson-wolinsky:96}.
In our approach, we consider the topologies of certain standard
networks (such as complete network, cycle or shared network, star
network, multi-partite networks) and then study whether such
topologies are pairwise stable following the framework of NFGL.
The main advantage of this approach is that it is not limited by
the number of nodes or edges in the network. However, in this approach, 
starting from some initial configuration of a network, the resultant topology of pairwise
stable network may not be any of these standard networks. In other
words, there could exist certain other topologies that satisfy
pairwise stability apart from these standard networks. However, as
we shall see from the empirical results, this approach indeed
results in a satisfactory answer.

We now present a series of results to establish certain standard
networks are pairwise stable.
\vspace{-0.1in}
\begin{lemma}
\label{lem:StabilityConditions1} If $(\delta-c)\leq\delta^{2}$ and
$(c-\delta)\leq\delta^{2}$, then the complete bipartite network is
pairwise stable.
\end{lemma}

\begin{proof}
% The outline of proof is very similar in all the four cases. For brevity,
% we only prove (d) here:
%%%%%%%%%%%%%%%%%%nrsuri comment begins
% \begin{figure}[h]
% %
% %\begin{minipage}[t]{0.33\columnwidth}%
% %\includegraphics[scale=0.33]{Figures/CompleteBipartite}
% %
% %\vspace{0.1in}
% %\centering
% %\small
% %\text{$(a)$}%
% %\end{minipage}%
% \begin{minipage}[t]{0.53\columnwidth}%
% \includegraphics[scale=0.33]{Figures/CompleteBipartite-ExtraEdge}
%
% \vspace{0.1in}
% \centering
% \small
% \text{$(a)$}%
% \end{minipage}%
% \begin{minipage}[t]{0.33\columnwidth}%
% \includegraphics[scale=0.33]{Figures/CompleteBipartite-EdgeRemoved}
%
% \vspace{0.1in}
% \centering
% \small
% \text{$(b)$}%
% \end{minipage}
%
% \caption{$(a)$ After adding a new edge $ij$ $(b)$ After deleting edge $il$\label{fig:complete-bipartite-network-abc}}
%
% \end{figure}

%%%%%%%%%%%%%%%%%%%%%%%nrsuri comment ends
Consider a complete bipartite network, $G$,  with $a_1$ and $a_2$
nodes respectively in the two partitions. The utility of node $i$
in a partition with $a_1$ nodes is
$u_{i}(G)=a_{2}(\delta-c)+a_{2}\delta^{2}$. This lemma can be
proved in two steps.\\
{\em Step 1:} Let us now add the edge $(i,j)$ to $G$ and call the
resultant graph $\overline{G}$. It can be readily checked that
$u_i(\overline{G}) = (a_{2}+1)(\delta-c)+(a_{2}-1)\delta^{2}$.
Since we are given that $\delta^{2} \geq (\delta-c)$, we get that
$u_i(G) = a_{2}(\delta-c)+a_{2}\delta^{2} \geq
(a_{2}+1)(\delta-c)+(a_{2}-1)\delta^{2} = u_i(\overline{G})$. That
is, no pair of non-neighbor nodes is better off by forming a
link in $G$.\\
{\em Step 2:} Assume that node $i$ severs an edge in $G$ and call
the resultant graph $\hat{G}$. It can be shown that
$u_{i}(\hat{G})=(a_{2}-1)(\delta-c)+(a_{2}-1)\delta^{2}$. Since we
are given that $\delta^{2} \geq (\delta-c)$, it is immediately seen
that $u_i(G) \geq u_i(\hat{G})$. Node $i$ is not better off by 
severing a link in $G$.

Note that we can apply similar analysis with respect to each node
in the other partition. Hence the complete bipartite network is
pairwise stable.
\end{proof}

\begin{lemma}
\vspace{-0.07in}
\label{lem:StabilityConditions} (a) The complete network is pairwise stable if
$(c-\delta)\leq0$ (b) The shared (cycle) network is pairwise stable if
$1\leq(c-\delta)/\delta^{2}\leq2$, (c) The null (empty) network is
pairwise stable if $(\delta-c)\leq0$.
\end{lemma}
The result can be proved easily by using arguments similar to
that in Lemma \ref{lem:StabilityConditions1}.
\vspace{-0.07in}
\begin{lemma}\label{kpartite-result}
For all $k \geq 3$, the complete $k$-partite network is pairwise
stable if (i) $\delta = c$, and (ii) $a_i=a, \forall i \in \{
1,2,...,k\}$ where $a_i$ is the number of nodes in partition $i$
in \text{$k$-partite} network and $a$ is any positive integer.
\end{lemma}
\begin{proof}
We start with a $k$-partite graph, $G$, satisfying condition (ii)
given in the statement of this lemma. Consider a node $i$ in the 
$p^{th}$ partition of $G$ where $1\leq p \leq k$. We construct the
proof in two steps.

\textit{Step 1 (edge addition): } We can see that, in $G$,  the
only link that can be added from node $i$ is to a node $j$ in the
$p^{th}$ partition. Let $\overline{G}$ be the network obtained
after a new link $(i,j)$ is added to $G$. For pairwise stability,
we need $u_{i}(\overline{G}) - u_{i}(G) \leq 0 $. This implies
\vspace{-0.05in}
\begin{multline}
\nonumber (\delta-c) + (d_i +1) \delta^2 \Biggl( 1 - \frac{\sigma_i^{'}}{\binom{d_i+1}{2}} \Biggr) - d_i\delta^2 \Biggl( 1 - \frac{\sigma_i}{\binom{d_i}{2}} \Biggr) \leq 0
\vspace{-0.01in}
\end{multline}
where $\sigma_i^{'}$ is the number of links among the neighbours
of node $i$ in $\overline{G}$ and $\sigma_i$ is the number of
links among the neighbours of node $i$ in $G$. Note that $d_i =
d_j$ since nodes $i$ and $j$ belong to the same partition in $G$.
Now we get that $\sigma_i^{'} = \sigma_i + d_j = \sigma_i + d_i $.
% \begin{align}
% \nonumber (\delta-c) + (d_i +1) \delta^2 \Biggl( 1 - \frac{\sigma_i+d_i}{\binom{d_i+1}{2}} \Biggr) - d_i\delta^2 \Biggl( 1 - \frac{\sigma_i}{\binom{d_i}{2}} \Biggr) \leq 0
% \end{align}
Simplifying, we get
\begin{align}
\label{lamma-ps-eqn} u_{i}(\overline{G}) - u_{i}(G) = (\delta-c) -
\delta^2 + \delta^2 \Biggl(\frac{2 \sigma_i}{d_i(d_i-1)}\Biggr)
\end{align}
Since the term $\displaystyle\frac{2\sigma_i}{d_i(d_i-1)}$ lies in
the interval $[0,1]$ and the fact that $\delta = c$ (given in the
statement of this lemma), we get that expression
(\ref{lamma-ps-eqn}) is non-positive. This implies that no pair of
nodes can form a link to improve their respective utilities.

\textit{Step 2 (edge deletion): } In $G$, consider that node $i$
deletes a link to a node $j$ in the $q^{th}$ partition where $1
\leq q \leq k$ and $p\neq q$. Let $\overline{G}$ be the network
obtained after the link $(i,j)$ has been deleted from $G$. For
pairwise stability, we need $u_{i}(\overline{G}) - u_{i}(G) \leq 0
$. This implies
\begin{multline}
\nonumber -(\delta-c) + (d_i -1) \delta^2 \Biggl( 1 - \frac{\sigma_i^{'}}{\binom{d_i-1}{2}} \Biggr) - d_i\delta^2 \Biggl( 1 - \frac{\sigma_i}{\binom{d_i}{2}} \Biggr) \leq 0
\end{multline}
where $\sigma_i^{'}$ denotes the number of links among the neighbours of node $i$ in $\overline{G}$. We can see that $\sigma_i^{'} = \sigma_i -d_j + a_i$. Simplifying,
\begin{align}\label{deletionedge}
-(\delta-c) - \delta^2 + \delta^2 \underbrace{\Bigl(\frac{-2 \sigma_i + 2d_j-2a_i}{d_i-2} + \frac{2 \sigma_i}{d_i -1}\Bigr)}_{expr_1} \leq 0
\end{align}
We know that $d_i = \sum_{j\neq i} a_j$.
\begin{align}\label{sigmai}
\sigma_i &= \binom{d_i}{2} - \sum_{j\neq i} \binom{a_j}{2} &= \frac{d_i^2 - \sum_{j \neq i} a_j^2}{2}
\end{align}
Now, using the above expression for $\sigma_i$, we can show that $expr_1 \leq 1$ using proof by contradiction.
We are given that $\delta=c$. Thus, from equation~(\ref{deletionedge}),
\begin{align}\label{deletionedge2}
\nonumber - \delta^2 + \delta^2 \underbrace{\Bigl(\frac{-2 \sigma_i + 2d_j-2a_i}{d_i-2} + \frac{2 \sigma_i}{d_i -1}\Bigr)}_{\leq 1} &\leq 0 \\
\Rightarrow u_{i}(\overline{G}) - u_{i}(G) &\leq 0
\end{align}
Thus, node $i$ does not have any incentive to add an edge to $G$
or delete an edge from $G$ when the conditions given in the
statement of the lemma are satisfied. As node $i$ is chosen
arbitrarily from $G$, we have that $G$ is pairwise stable.
\end{proof}
\vspace*{-0.14in}

%\begin{lemma}
%The complete network is pairwise stable if and only if $\delta > c$ \text{ and }  $(\delta - c) \geq \delta^2 $.
%\end{lemma}
%\vspace*{-0.1in} {\bf Sketch of the Proof:} {\em (only if part)
%Given a complete network, there is no incentive to delete a link
%as the loss from deleting a link is greater than the loss that
%would accrue from decrease in bridging benefits.
%
%(if part) Given any arbitrary network, the addition of a link
%to/from any node strictly increases its payoffs and this process
%continues till the complete network is formed.}

\vspace*{0.2cm} Using a similar approach, we can prove the
stability results for other standard networks. Due to space
constraints, we only summarize these results in
Table~\ref{summarytable2}.

% \begin{table}[]
% \caption{{\textbf{Characterization of Network Structures under the Utility Model}}}\label{summarytable2}
% \vspace{0.1in}
% \centering
% \begin {tabular} {|c |c|}
% \hline
% {CONDITIONS} & {RESULTS} \\
% \hline
% &\\
% $\delta > c$, $(\delta - c) > \delta^2 $ & Complete network is pairwise stable. \\
% &\\
% \hline
% $\delta > c$, $(\delta - c) < \delta^2 $ & Complete network is pairwise stable. \\
% &\\
% & Complete bipartite network is pairwise stable. \\
% & \\
% \hline
% $\delta = c$ & Complete network is pairwise stable. \\
% & Shared network is pairwise stable. \\
% & Null network is pairwise stable. \\
% & Complete bipartite network is pairwise stable. \\
% & \\
% \hline
% $(\delta = c)$ and $a_i=a, \forall i \in K$& \\
% where $k \geq 3 \text{ and } a \in \{1,2,...\}$& Complete k-partite graph is pairwise stable.\\
% \hline
% $(\delta < c)$ & Null network is pairwise stable \\
% & \\
% \hline
% % $(\delta < c)$ and $ \displaystyle\frac{c-\delta}{\delta^2} \leq 2 $ & Shared network is pairwise stable. \\
% % &\\
% % \hli
% $(\delta < c)$ and $ 2 \geq \displaystyle\frac{c-\delta}{\delta^2} \geq 1 $ & Shared network is pairwise stable.\\
% & \\
% \hline
% $(\delta < c)$ and $ \delta^2 \geq (c-\delta)$& Complete bipartite network is pairwise stable \\
% &\\
% \hline
% &\\
% $(\delta < c)$ and $a_i=a, \forall i \in K$& \\
% where $k \geq 3$ and $a \in \{1,2,...\}$ & Complete k-partite graph is pairwise stable.\\
% &\\
% \hline
% &\\
% $(\delta - c) \leq \bigl(\frac{2}{3}\times \delta^2 \bigr)$ and & \\
% $a_1=a_2=a_3=a$ where $a \in \{1,2,...\}$ & Complete 3-partite graph is pairwise stable.\\
% &\\
% \hline
% \end {tabular}
% \end{table}

% \begin {itemize}
% \item When $\delta > c$, $(\delta - c) \geq \delta^2 $, the complete graph is a pairwise stable network.
% \item When $\delta > c$, $(\delta - c) < \delta^2 $, the complete network and complete bipartite network  are pairwise stable networks.
% \item When $\delta = c$, complete network, shared network, null network and complete bipartite network  are  pairwise stable networks.
% \item When $(\delta = c)$ and $a_i=a, \forall i \in K$ where $k \geq 3 \text{ and } a \in \{1,2,...\}$, complete k-partite network is a pairwise stable network.
% \item When $(\delta < c)$, null network  is a pairwise stable network.
% \item When $(\delta < c)$ and $ 2 \geq \displaystyle\frac{c-\delta}{\delta^2} \geq 1 $, shared network is a pairwise stable network.
% \item When $(\delta < c)$ and $ \delta^2 \geq (c-\delta)$, complete bipartite network  is a pairwise stable network.
% \item When $(\delta - c) \leq \bigl(\frac{2}{3}\times \delta^2 \bigr)$ and $a_1=a_2=a_3=a$ where $a \in \{1,2,...\}$, complete 3-partite network is a pairwise stable network.
% \end {itemize}

%
% % \begin{table}[h]
% % \centering
% % % \begin{minipage}{9cm}
% % \caption{{\textbf{Characterization of Network Structures \text{under} the proposed utility Model}}}\label{summarytable2}
% % \vspace{0.1in}
% % \small
% % \begin {tabular} {||l||l||l||l||l||}
% % \hline
% % \hline
% % {\textbf{Parameter }}  & {\textbf{Pairwise-Stable }} & \textbf{N}\footnotemark[1] & \textbf{S}\footnotemark[2] \\
% % {\textbf{Range}}  & {\textbf{networks}} & {\textbf{}} &{\textbf{}} \\
% % \hline
% % \hline
% % % &\\
% % \multirow{3}{*}{\begin{sideways}$\delta > c$\end{sideways}}& $(\delta - c) < \delta^2$ & Complete bipartite or complete & $x$ & $\checkmark$\\ & $(\delta - c) \geq 2/3\delta^2 $ & Complete Equi-3-paritite& $x$ & $\checkmark$\\ & $(\delta - c) \geq \delta^2$& Complete & $\checkmark$ & $\checkmark$\\& & \cr \hline & $x$ & $\checkmark$
% % % &\\
% % \hline
% & \\
% \begin{sideways}Paper\end{sideways}&& Complete or & & \\
% \begin{sideways}Paper\end{sideways}&$\delta > c$, $ & Complete bipartite & x & $\checkmark$ \\
% & & & & \\
% \hline
% \begin{sideways}Paper\end{sideways}& & Complete or & & \\
% \begin{sideways}Paper\end{sideways}& $\delta > c$, $(\delta - c) < \delta^2 $ & Complete bipartite & x & $\checkmark$ \\
% \begin{sideways}Paper\end{sideways}& & Complete equi-3-partite & & \\
% & & & & \\
% \hline
% % & \\
% \begin{sideways}Paper\end{sideways}&$\delta = c$  & Complete, & x & $\checkmark$ \\
% \begin{sideways}Paper\end{sideways}& & Shared or  Null or   & & \\
% \begin{sideways}Paper\end{sideways}& &Complete bipartite or & & \\
% &Complete equi-$k$-partite & & \\
% % & \\
% \hline
% % & \\
% % $(\delta = c)$ & & x & $\checkmark$ \\
% % and $a_i=a, \forall i \in K$ & Complete $k$-partite & & \\
% % where $k \geq 3 \text{ and }$ & & & \\
% % $a \in \{1,2,...\}$ & & & \\
% % & \\
% % \hline
% % &\\
% $(\delta < c)$ & Null & x & $\checkmark$ \\
% % & \\
% \hline
% % $(\delta < c)$ and $ \displaystyle\frac{c-\delta}{\delta^2} \leq 2 $ & Shared network is pairwise stable. \\
% % &\\
% % \hli
% $(\delta < c)$ & & x & $\checkmark$ \\
% and $ \delta^2 \leq (c-\delta) \leq 2\delta^2 $ & Shared & & \\
% % & \\
% \hline
% % & \\
% $(\delta < c)$ and & & x & $\checkmark$ \\
% $ \delta^2 \geq (c-\delta)$ & Complete bipartite & & \\
% % &\\
% \hline
% % &\\
% % & $(\delta < c)$ and $a_i=a, \forall i \in K$ \\
% % Complete k-partite network  & where $k \geq 3$ and $a \in \{1,2,...\}$ \\
% % &\\
% % \hline
% % &\\
% $(\delta - c) \leq \bigl(\frac{2}{3}\times \delta^2 \bigr)$, & & x & $\checkmark$\\
% $a_1=a_2=a_3=a$ & Complete 3-partite & & \\
%  where $a \in \{1,2,...\}$   & & & \\
% % &\\
% \hline
% \hline
% \end {tabular}
%
% \footnotemark[1]{\textbf{N:} Necessary Condition}
% \footnotemark[2]{\textbf{S:} Sufficient Condition}
% % \end{minipage}
% \vspace{-0.2in}
% \end{table}
% We summarize the pairwise stability results in Table~\ref{summarytable2}.
\begin{table}[h]
\centering
% \begin{minipage}{9cm}
\caption{{\textbf{Characterization of Network Structures \text{under} the proposed utility Model}}}\label{summarytable2}
\vspace{0.1in}
\small
\begin {tabular} {||l||l||l||}
\hline
\hline
{\textbf{Parameter }}  &  {\textbf{Additional }} &{\textbf{P.S.}\footnotemark[1]} \\
{\textbf{Region}}  & {\textbf{Conditions}}&{\textbf{networks}} \\
\hline
\hline
% &\\
\multirow{5}{*}
& $\textbf{(1a) }(\delta - c) \geq \delta^2$ & Complete \tabularnewline
\cline{2-3}
$\textbf{(1) }\delta > c$ & $\textbf{(1b) }(\delta - c) < \delta^2$ & Complete \\
& & C.B.P \footnotemark[4] \\
\cline{2-3}
& $\textbf{(1c) } (\delta - c) < 2/3\delta^2$ & C.E.T.P \footnotemark[6] \\
& & Complete \\
& & C.B.P \\
% & & Complete & x & $\checkmark$\\
\cline{2-3}
\hline
\multirow{4}{*}
& & Complete \\
\textbf{(2) }$\delta = c$ & & C.B.P \\
& & Shared \\
& & C.E.K.P \footnotemark[5] \\
& & Null \\
\hline
\multirow{5}{*}
& $\textbf{(3a) } (c - \delta) > 2\delta^2$& Null \\
\cline{2-3}
& $\textbf{(3b) }(c - \delta) \leq \delta^2$  & C.B.P \\
& & Null \\
\cline{2-3}
\textbf{(3) }$\delta < c$ & $\textbf{(3c) }\delta^2 \leq (c - \delta) \leq 2\delta^2$  & Shared \\
& & Null \\
\cline{2-3}
& $\textbf{(3d) }(c - \delta) < 2/3\delta^2$ & C.E.T.P \\
& & Null \\
& & C.B.P \\
\hline
\hline
% & & Complete bipartite & $x$ & $\checkmark$\\
% & $(\delta - c) \geq 2/3\delta^2 $ & Complete Equi-3-paritite& $x$ & $\checkmark$\\ & $(\delta - c) \geq \delta^2$& Complete & $\checkmark$ & $\checkmark$\\& & & $x$ & $\checkmark$
% % &\\
\end {tabular}



\footnotemark[1]{\textbf{P.S:} Pairwise Stable}
% \footnotemark[1]{\textbf{P.R:} Parameter Range }
\footnotemark[4]{\textbf{C.B.P: } Complete BiPartite }

\footnotemark[5]{\textbf{C.E.K.P : } Complete Equi $k$-Partite }

\footnotemark[6]{\textbf{C.E.T.P : } Complete Equi 3-Partite }
% \end{minipage}
\vspace{-0.2in}
\end{table}


\begin{figure}[htb!]
\vspace{0.2in}
\begin{tabular}{cccc}
\begin{minipage}{4 cm}
\centering
\includegraphics[scale=0.4]{Figures/GraphicalIllustration}
\end{minipage}
\end{tabular}
\caption{Analytical results on pairwise stability. Note: The legends in the figure correspond to the numbering specified in Table~\ref{summarytable2}. \label{fig:Analytical-Regions-of-stability}}
\end{figure}

% \begin{table}[h]
% \centering
% % \begin{minipage}{9cm}
% \caption{{\textbf{Characterization of Network Structures \text{under} the proposed utility Model}}}\label{summarytable2}
% \vspace{0.1in}
% \small
% \begin {tabular} {||l||l||l||l||}
% \hline
% \hline
% {\textbf{Parameter }}  & {\textbf{Pairwise-Stable }} & \textbf{N}\footnotemark[1] & \textbf{S}\footnotemark[2] \\
% {\textbf{Range}}  & {\textbf{networks}} & {\textbf{}} &{\textbf{}} \\
% \hline
% \hline
% % &\\
% $\delta > c$, $(\delta - c) \geq \delta^2 $ & Complete & $\checkmark$ & $\checkmark$\\
% % &\\
% \hline
% % & \\
% & Complete & & \\
% $\delta > c$, $(\delta - c) < \delta^2 $ & Complete bipartite & x & $\checkmark$ \\
% & & & \\
% \hline
% % & \\
% $\delta = c$  & Complete, & x & $\checkmark$ \\
% & Shared, Null,  & & \\
% &Complete bipartite & & \\
% % & \\
% \hline
% % & \\
% $(\delta = c)$ & & x & $\checkmark$ \\
% and $a_i=a, \forall i \in K$ & Complete k-partite & & \\
% where $k \geq 3 \text{ and }$ & & & \\
% $a \in \{1,2,...\}$ & & & \\
% % & \\
% \hline
% % &\\
% $(\delta < c)$ & Null & x & $\checkmark$ \\
% % & \\
% \hline
% % $(\delta < c)$ and $ \displaystyle\frac{c-\delta}{\delta^2} \leq 2 $ & Shared network is pairwise stable. \\
% % &\\
% % \hli
% $(\delta < c)$ & & x & $\checkmark$ \\
% and $ 2 \geq \displaystyle\frac{c-\delta}{\delta^2} \geq 1 $ & Shared & & \\
% % & \\
% \hline
% % & \\
% $(\delta < c)$ and & & x & $\checkmark$ \\
% $ \delta^2 \geq (c-\delta)$ & Complete bipartite & & \\
% % &\\
% \hline
% % &\\
% % & $(\delta < c)$ and $a_i=a, \forall i \in K$ \\
% % Complete k-partite network  & where $k \geq 3$ and $a \in \{1,2,...\}$ \\
% % &\\
% % \hline
% % &\\
% $(\delta - c) \leq \bigl(\frac{2}{3}\times \delta^2 \bigr)$, & & x & $\checkmark$\\
% $a_1=a_2=a_3=a$ & Complete 3-partite & & \\
%  where $a \in \{1,2,...\}$   & & & \\
% % &\\
% \hline
% \hline
% \end {tabular}
%
% \footnotemark[1]{\textbf{N:} Necessary Condition}
% \footnotemark[2]{\textbf{S:} Sufficient Condition}
% % \end{minipage}
% \vspace{-0.2in}
% \end{table}

\subsection{Simulation Results}\label{sec:Simulations}

In this section, we present results of our simulation study. The
purpose of these simulations is two-fold. First, from the above
theoretical analysis (Table~\ref{summarytable2}), it cannot be
concluded that the analytical predictions of the network
topologies are unique. Moreover, the list of pairwise stable
networks is not exhaustive. Second, our analysis does not capture
the dynamics of how links form and get deleted based on rules of
NFGL.


\begin{figure*}[htb!]
\begin{tabular}{cccc}
\begin{minipage}{4 cm}
\centering
\includegraphics[scale=0.2]{Figures/std1}
\end{minipage}
\hspace{0.1in}
&
\hspace{-0.2in}
\begin{minipage}{4 cm}
\centering
\includegraphics[scale=0.2]{Figures/std2}
\end{minipage}
\hspace{0.1in}
&
\hspace{-0.2in}
\begin{minipage}{4 cm}
\centering
\includegraphics[scale=0.2]{Figures/std3}
\end{minipage}
\hspace{0.1in}
&
\begin{minipage}{4 cm}
\centering
\includegraphics[scale=0.2]{Figures/std4}
\end{minipage}
\\
(a) & (b) & (c) & (d)
\end{tabular}
\caption{Regions of stability of some standard networks\label{fig:Expected-Regions-of-stability}}
\end{figure*}

\begin{figure*}[htb!]
\begin{tabular}{ccc}
\begin{minipage}{6 cm}
\centering
\includegraphics[scale=0.28]{Figures/fig1}
\end{minipage}
&
\hspace{-0.2in}
\begin{minipage}{6 cm}
\centering
\includegraphics[scale=0.28]{Figures/fig2}
\end{minipage}
&
\hspace{-0.2in}
\begin{minipage}{6 cm}
\centering
\includegraphics[scale=0.28]{Figures/fig3}
\end{minipage}
\\
(a) & (b) & (c)
\end{tabular}
\caption{Network Topologies obtained during simulations in 10-agent networks \label{fig:Simulation-Results-N=00003D10}}
\vspace{-0.2in}
\end{figure*}

\subsubsection{Simulation Setup}
%
% We built a custom simulator using the C++ programming language. To implement the standard graph routines, we used the BOOST C++ libraries~\cite{boost}  which has efficient implementations of fundamental graph data structures and routines.

We start with a random initial network consisting of $n$ agents.
The number of edges between these agents is determined by the
parameter $density (\gamma)$. For example, if $\gamma = 0$, we
start with an empty network; if $\gamma = 0.35$, we start with a
network that contains $35\%$ of the possible $\binom{n}{2}$ edges.
These edges are chosen uniformly at random.

% As noted in Section~\ref{utilitymodel}, for an agent, maintaining a direct edge with another agent  brings him a benefit of $\delta$ $(0<\delta\leq1)$ and costs him $c$ $(0<c\leq1)$. In addition, each agent reaps additional indirect benefit because of his potential to bridge his unconnected neighbours (determined by sparsity of relationships among his neighbours).



Each agent is given an opportunity to act, based on a random schedule. We have run simulations for networks  with $3,\ 4,\ 5 \text{ and }10$ agents. However, due to space constraints, we only discuss the results for $10$-agent networks.  Each agent, when scheduled, considers three actions - namely, add an edge to an agent that he is not directly connected to, delete an existing edge to an agent, or do nothing. Each agent chooses the action that maximizes his individual payoff, breaking ties randomly. Note that agent $i$, when adding an edge to agent~$j$, is allowed to do so only if it is beneficial to both or if agent $j$ is  not worse off. However, agent $i$, when deleting an existing edge to agent $j$, is allowed to do so unilaterally. We define one \textit{iteration} as a scenario in which each agent has been given exactly one opportunity to act.

At some stage, the network could evolve into a stable state where
no agent has any incentive to modify the network. One iteration in
which no agent modifies the network is an \textit{idle iteration},
and the parameter \textit{Num-Idle-Terminate}($=1$ in our
simulations) indicates the number of idle iterations before we
conclude that the network has reached a stable state. This is the
case of normal termination of a simulation run. However, there may
be cases where the network does not emerge into a stable state and
cycles through  previously visited states even after many
iterations (the case of \textit{dynamic-equilibrium} as noted in
Hummon~\cite{hummon00}). The parameter \textit{Max-Iterations}
($=1000$  in our simulations) indicates the number of iterations
before we forcibly terminate the simulation run. The parameter
\textit{Num-Repetitions} (=100 in our simulations) indicates the
number of times the experiment was repeated. The simulations were
averaged out over different initial conditions and random
schedules.
% To average out results that are only due to chance and to improve the accuracy of simulation results, each simulation run is repeated \textit{Num-Repetitions}($=100$ in the simulations) times.

% Once the network reaches a stable state, we classify the network structure as one of the following - \textit{Null, Star, Shared, Complete, Near-Null, Near-Star, Near-Shared, Near-Complete, k-partite, k-partite\: complete}. As in Hummon~\cite{hummon00}, we use the sorted (descending order) degree vector to characterize the structure of the stable network. For example, the Null network has a sorted degree vector of (0, 0, \ldots{}, 0), the Star network (n-1, 1, 1, \ldots{}, 1), the Shared network (2, 2, \ldots{}, 2), and the Complete network (n-1, n-1, \ldots{}, n-1). Also as in Hummon~\cite{hummon00}, we use total mean squared
% deviation (MSD) to classify the resultant stable network as Near-\textquotedbl{}standard network\textquotedbl{} (for example, Near-complete network).

%%%%%%%%%%%%%%%%%%%nrsuri comment begins

%%%%%%%%%%%%%%%%%%nrsuri comment ends

% The following example clarifies this procedure:Consider the 5-agent network in Figure \ref{fig:5-agent-network}. This network is a Complete network except for the 2 missing edges BE and DE. Therefore, we would like to classify this network as Near-Complete. This is done as follows. For this network, the sorted degree vector is (4, 4, 3, 3, 2). The total MSD of this network from Star network is 3.6 $=((4-4)^{2}+(4-1)^{2}+(3-1)^{2}+(3-1)^{2}+(2-1)^{2}))/5$. Similarly, the total MSD from Null network is 10.8, the total MSD from Shared network is 2, and the total MSD from the Complete Network is 1.2. The metric 1.2 being the least among these, we classify the above network structure as Near-Complete.

% \subsection{Metrics Recorded\label{sub:Metrics-Recorded}}
%
% At the end of \textit{Num-Repetitions} number of repetitions, the following
% metrics were recorded.
% \begin{enumerate}
% \item The network structure (shape) for each repetition
% \item The frequency with which each of the network structures in Section
% \ref{sub:Classification-of-Network-Structures} resulted (across all
% repetitions)
% \item The mean utility of the final network (across all repetitions)
% \item The mean time to reach the final network (across all repetitions)
% \item The mean number of acts to reach the final network (across all repetitions)
% \end{enumerate}


\subsubsection{Simulation Results}

Based on the theoretical results provided earlier, Figure \ref{fig:Expected-Regions-of-stability} shows the expected regions of stability for some standard networks. We note that, in all figures presented in this section, the vertical axis is the benefit $(\delta)$ and horizontal axis is the cost $(c)$.
%of each sub-figure in Figure \ref{fig:Expected-Regions-of-stability} is the benefit value ($\delta$), ranging %from 0.05 to 1, and the horizontal axis represents the cost parameter ($c$), ranging from 0.05 to 1.
The shaded region is the region in which the corresponding graph is stable.

Figure \ref{fig:Simulation-Results-N=00003D10} shows the simulation results for 10-agent networks.
% The vertical axis of each sub-figure in Figure \ref{fig:Simulation-Results-N=00003D10} is the benefit value ($\delta$), ranging from 0.05 to 1, and the horizontal axis represents the cost parameter ($c$), ranging from 0.05 to 1. As noted earlier, for a $<c,\delta>$ pair, we repeat the simulation for \textit{Num-Repetitions}.
Each repetition for the simulation results in a network that can be classified as one of the structures mentioned in the theoretical analysis. We plot the most frequent (modal) network structure as determined by the frequency with which each of the network structures resulted in \textit{Num-Repetitions} simulation runs. The experiment was repeated starting with different network densities, $\gamma=0, 0.35 \text{ and } 0.7$.

In each of the sub-figures in Figure~\ref{fig:Simulation-Results-N=00003D10}, we observe that the complete graph is the resultant pairwise stable network (when $\delta > c$, $(\delta - c) \geq \delta^2 $) which  concurs with the theoretical predictions that the complete graph is the unique pairwise stable network in this region (Table~\ref{summarytable2}). We can also infer from Figure~\ref{fig:Expected-Regions-of-stability} that there is an overlap in the stability regions of each of the three networks - complete, null and shared - with that of the complete bipartite network. However, as observed through simulations, we see that the complete $k$-partite network (which includes the complete bipartite network) emerges as the \textit{modal} pairwise stable network in its regions of overlap with the three aforementioned networks (Figure~\ref{fig:Simulation-Results-N=00003D10}(b) and Figure~\ref{fig:Simulation-Results-N=00003D10}(c)). This can be attributed to the fact there are a large  number of possible bipartite graphs whereas there is only one null network, one complete network and the shared network is a special instance of a $k$-partite network. Hence, the likelihood of the null, complete and  shared networks emerging in a region where the bipartite network is also pairwise stable, is small. We can also observe from  Figure~\ref{fig:Simulation-Results-N=00003D10}(b) and Figure~\ref{fig:Simulation-Results-N=00003D10}(c) that, in some regions, we get the non-complete $k$-partite network as a pairwise stable network. This is a new finding from our simulations which justifies our earlier remark that simulations can lead to pairwise stable networks not predicted theoretically.

Thus, we see that simulation studies not only validate the theoretical results but also enables a better understanding of the dynamics of network evolution.


% We can note in Figure \ref{fig:Expected-Regions-of-stability} that there is an overlap of regions of stability of Null and Complete bipartite networks (i.e., Complete K-Partite with $k=2$). Looking at Figure~\ref{fig:Simulation-Results-N=00003D10}(b) and Figure~ \ref{fig:Simulation-Results-N=00003D10}(c), the Complete K-Partite (with $K=2$) network dominates the Null network (in the region of their overlap), because of the high density of number of edges in the initial network. There are 10! (=3628800) possible bipartite graphs where as there is only one Empty network. Hence, the likelihood of the Null network emerging in a region where the bipartite network is also pairwise stable is small. However, when the $\gamma$ is zero (Figure \ref{fig:Simulation-Results-N=00003D10}(a)), the Null network is already the pairwise stable network hence emerges as one from the simulation. From Figures \ref{fig:Expected-Regions-of-stability}(c) and \ref{fig:Expected-Regions-of-stability}(d), there is an overlap of regions of stability of Shared and Complete bipartite networks. However, from Figure \ref{fig:Simulation-Results-N=00003D10}, we see that the Complete bipartite network dominates the Shared network in all the cases. The Shared network is only a special instance of a bipartite network. From Figure \ref{fig:Expected-Regions-of-stability}, there is an overlap of regions of stability of Complete and Complete bipartite networks. From Figure \ref{fig:Simulation-Results-N=00003D10}, we see that the Complete bipartite network dominates a major portion of this region of overlap, as, for a 10-agent network, there is only one Complete network, where as there are 3628800 Complete bipartite graphs. However, as the density of the initial network increases, the likelihood of getting Complete network increases.

% Response: It may be difficult to conclude why all graphs are converging to complete.
% it basically depends on the structure as well as the number of edges in the initial network.
% I think right now we need not reason this to such detail.
%
%  \textbf{TODO: <Subbu and Rohith> According to this logic , the complete-bipartite
% network should totally totally dominate the Complete network in the
% region of overlap. What do you think is the reason why we don't see
% this behavior. Do you suspect anything wrong in the region of stability
% of the Complete equi-bipartite network as depicted in Figure \ref{fig:Expected-Regions-of-stability}?}
%

% Response: We are not adding for lower nodes. Higher nodes ( more than 10) are more interesting.
% \textbf{TODO: <We could add graphs for 3, 4, and 5 agent network also,
% if we are putting the paper in a journal>}

%The deviation of simulation results in Figure \ref{fig:Simulation-Results-N=00003D10}
%from the expected results in Figure \ref{fig:Expected-Regions-of-stability}
%could be attributed to the factor of network dynamics. Some aspects
%of network dynamics are - the state of the initial network before
%starting the simulation (i.e. the exact nature of pre-existing edges),
%the relative order in which each agent gets an opportunity to act
%(which determines the prevailing network structure when an agent gets
%to act), etc. The reader is referred to Hummon~\cite{hummon00}, for
%more details on the effects of network dynamics.




% We also see that the graphs that emerge in simulation match one of the predicted stable graphs \footnote{(TODO: We need to identify exceptions if any, Srinath's results had all the experiments combined we will try to check only for MA-UD}



% \vspace{-0.1in}
\section{Structure of Efficient Networks}\label{sec:Efficiency}

In this section, we study the structure of efficient networks, i.e., networks that maximize the
overall utility, under various conditions of $\delta$ and $c$. First, we begin by introducing some very useful classical results in extremal graph theory which will be used later in our analysis.

\vspace{-0.05in}
\subsection{Triangles in a Graph}
% We first give the definition of a \textit{Turan's graph}.
%\begin{definition}[Turan graph]
%Let $G=(V,E)$ be a simple graph with $n$ vertices and edge set $E$. Divide $V$ into $(p-1)$ pairwise disjoint subsets $V=V_1 \cup V_2 \cup \ldots \cup V_{p-1}$, $n_i = |V_i|$, $n = n_1+n_2+\ldots+n_{p-1}$. There is an edge joining two vertices if and only if the vertices lie in distinct sets $V_i, V_j$. We denote the resulting graph by $K_{n_1, \ldots, n_{p-1}}$; it has $\sum_{i<j} n_i n_j$ edges.
%We call $K_{n_1, \ldots, n_{p-1}}$ with $|n_i - n_j| \leq 1, \forall i, j \in \{1, \ldots, (p-1)\}$ as a \text{Turan graph}.
%\end{definition}
% \subsubsection{Triangles in Graph}

If three nodes $i$, $j$, and $k$ in $G(V, E)$ are such that $i$
and $j$, $j$ and $k$, $k$ and $i$ are connected by edges, then we
say that nodes $i,j,k$ form a triangle in $G$. The number of
triangles in a simple graph $G$ plays a crucial role in the
computation of utilities to the nodes and we state here some
classical results. We know from Turan's theorem ~\cite{turan},
that it is possible to have a triangle free graph if the following
holds: \vspace{-0.1in}
\begin{equation}
\label{turantheorem} \vspace{-0.1in} e \le \bigg\lfloor
\frac{n^2}{4} \bigg\rfloor
\end{equation}
Here $e$ denotes the number of edges and $n$ the number of vertices of
the graph.  Moreover, from ~\cite{nor:ste}, we know that the number of triangles,
$T$, can be lower bounded, if the number of edges exceed the
above value $\lfloor \frac{n^2}{4} \rfloor $, by
\vspace{-0.1in}
\begin{equation} \label{theorem2}
T \geq \frac{n(4e-n^2)}{9}
\end{equation}

%\begin{theorem}[\cite{turan}] \label{turantheorem}
%If a graph $G=(V,E)$ on $n$ vertices has no p-clique ($p\geq2$), then
%\begin{align}
%|E| &\leq \left(1- \displaystyle \frac{1}{p-1}\right) \displaystyle \frac{n^2}{2}
%\end{align}
%\end{theorem}
%When $p=3$, the theorem states that a triangle-free graph on $n$ vertices contains at most $\displaystyle \Bigl\lfloor\frac{n^2}{4} \Bigr\rfloor$ edges. This is the result which we will use in our analysis below.
%
%We also use the following lower bound on the number of triangles possible in simple graphs due to ~\cite{nor:ste}.

%\begin{theorem}[\cite{nor:ste}]\label{theorem2}
%Let \\ \text{$G=(V,E)$} be a simple graph of $n$ vertices. The number of triangles $T$ in the graph when  $ |E| > \left(\displaystyle \frac{n^2}{4}\right)$
%is lower bounded by,
%\begin{align} \label{lowerbound}
%T &\geq \frac{n(4e-n^2)}{9}
%\end{align}
%\end{theorem}
%Summarizing the above two results, we have that, in a graph with $E>\displaystyle\frac{n^2}{4}$, the minimum number of triangles possible is non-zero and is \textit{tightly} lower-bounded by Equation~\ref{lowerbound} whereas, the Turan's theorem states that when $E\leq \displaystyle\frac{n^2}{4}$, it is possible to have a triangle-free graph.

%An equiparitioned complete bipartite graph (EBCG) is a complete bipartite graph wherein the number of nodes in the two components differ at most by 1. We can easily see that the EBCG belongs to the class of \textit{Turan graphs} (when $p=3$) and it has at most $n^2 / 4 $ edges (equality holds when $n$ is even). Henceforth, we will refer to EBCG as the Turan graph (denoted by $G_{Turan}$).

In what follows, we refer to the graph having maximum number of
edges with no triangles as the {\em Turan Graph} and we represent it
by $G_{Turan}$. It is easy to verify that such a graph is a
complete bipartite graph, and the the number of vertices in each
partition differs at most by $1$.

%Call this {\bf EBCG}, Equi-Bipartite Complete Graph.

% \subsection{ $\delta = c $ }
% Here we show that a Turan's graph maximizes the utility. Turan's graph
% also maximizes $\sum {d_i} $ and thus the total number of edges.
% It is a bipartite graph thus the second term is $1$, as the number of
% connected neighbours is nil.



\subsection{Finding the Efficient Graph}
\vspace{-0.1in}
\begin{definition}[Efficient Graph]
The utility ($u(G))$ of a given network $G$ is defined as the sum
of utilities of all the nodes (agents) in that network. That is,
\vspace{-0.15in}
\begin{align}
u(G) &= \sum_{i=1}^{n} u_{i}(G). \vspace{-0.2in}
\end{align}
A graph that maximizes the above expression (i.e. sum of utilities
of nodes) is called an efficient graph.
\end{definition}
We now present a series of results on the topologies of efficient
networks using the proposed framework. These results are based on
different ranges for the values of $\delta$ and $c$.

%As explained earlier, we can see the utility of a
%node has two components, one the utility from all its direct connections and a
%indirect utility due to the information flow among the dis-connected
%neighbours.

\vspace{-0.05in}
\begin{lemma}
When $ \delta <  c $ and $\delta^2 < (c - \delta)$, the null graph
is the unique efficient graph.
\end{lemma}
\begin{proof}
For any node $i$, $d_{i} > 0 $ implies that the utility of that
node is negative thus reducing the overall network utility.  This
follows from $(\delta - c + \delta^{2}) $ being negative.
\end{proof}
\vspace{-0.1in}
\begin{theorem}
\label{eff-thm-nrsuri} When $ \delta = c $, the Turan graph is the
unique efficient graph.
\end{theorem}

\begin{proof}
We will analyze the efficiency of an arbitrary graph (denoted by $G$) as follows.
\small{
\begin{align}
\vspace{-0.1in} \nonumber u(G) &= \sum_{i=1}^{n} u_{i}(G) =
\sum_{i=1}^{n} d_{i} \delta^{2} \left( 1 -
\displaystyle\frac{\sigma_{i}}{\binom{d_{i}}{2}} \right )
\vspace{-0.5in}
\end{align}
\vspace{-0.1in}
\begin{align}
\vspace{-0.5in}
\nonumber &= \delta^{2} \sum_{i=1}^{n} d_{i} - \delta^{2} \sum_{i=1}^{n}
                 \displaystyle\frac{2 \sigma_{i}}{(d_{i} - 1)}
\vspace{-0.1in}
\end{align}
\vspace{-0.1in}
\begin{align}
\vspace{-0.1in}
\nonumber & \le \delta^{2} \sum_{i=1}^{n} d_{i} - \frac{\delta^{2}}{(n-2)}
            \sum_{i=1}^{n} 2 \sigma_{i}
\vspace{-0.1in}
\end{align}
\vspace{-0.1in}
\begin{align}\label{efficiency_equation}
\vspace{-0.5in}
&=\delta^{2} \sum_{i=1}^{n} d_{i} - \frac{\delta^{2}}{(n-2)} (2 \times 3 \times T_{3}(G))
\vspace{-0.1in}
\end{align}}\normalsize
% \begin{multline}\label{efficiency_equation}
% \nonumber u(G) = \sum_{i=1}^{n} u_{i} = \sum_{i=1}^{n} d_{i} \delta^{2} \left( 1 - \displaystyle\frac{\sigma_{i}}{\binom{d_{i}}{2}} \right ) \\= \delta^{2} \sum_{i=1}^{n} d_{i} - \delta^{2} \sum_{i=1}^{n}               \displaystyle\frac{2 \sigma_{i}}{(d_{i} - 1)} \\
% \le \delta^{2} \sum_{i=1}^{n} d_{i} - \frac{\delta^{2}}{(n-2)} \sum_{i=1}^{n} 2 \sigma_{i} \\ =\delta^{2} \sum_{i=1}^{n} d_{i} - \frac{\delta^{2}}{(n-2)} (2 \times 3 \times T_{3}(G))
% \end{multline}
where, $T_{3}(G) $ is the number of triangles in the graph $G$. The last step
of the above simplification is due to the fact that the number of links
among the neighbours of a node $i$ is the number of triangles in the graph in
which node $i$ is one of the vertices of the triangle. The factor $3$ in the
last step is due to the fact that every triangle contributes to the
$\sigma_{i}$ of $3$ nodes. We know that, for an efficient graph, equation~(\ref{efficiency_equation}) should be maximized and that happens when the
number of triangles in a graph is minimized while simultaneously  maximizing
the number of edges in the graph.

%We also know from
%Theorem~\ref{turantheorem} that it is a triangle free graph with the maximal
%number of edges. It is clear just deleting edges from the Turan graph will only
%reduce the efficiency of the resultant graph when compared with the efficiency
%of the Turan graph. This is because deleting edges will reduce the utility got
%due to direct links and in addition, may introduce new triangles in the graphs
%which reduces the utility due to indirect links. So, there cannot be any graph
%with fewer edges than the Turan graph which yields a better efficiency value
%than Turan graph.
The Turan graph (refer equation~(\ref{turantheorem})) is a graph with
maximum edges that has no triangles.  So an efficient graph must
have an efficiency greater than or equal to that of a Turan graph.
Thus, it is clear that there is no need to consider graphs with
edges lesser than that of a Turan graph.  Let us consider the case
when a graph (denoted by $\overline{G}$) has more edges than the
Turan graph. Let $\overline{G}$ have $\lfloor \frac{n^2}{4}
\rfloor + x$ edges where $x>0$. From
equation~(\ref{efficiency_equation}), we know that \small{
\begin{align}\label{eqn5.5}
\nonumber u(\overline{G}) & = \sum_{i = 1}^{n}u_{i}(G) = \delta^{2} \displaystyle\sum_{i=1}^{n} d_{i} - \delta^{2} \displaystyle\sum_{i=1}^{n} \frac{2 \sigma_{i}}{(d_{i} - 1)} \\
&\le \delta^{2} \left(2 \left(\bigg\lfloor \frac{n^2}{4}
\bigg\rfloor +x\right)\right) - \frac{\delta^{2}}{(n-2)} (6
T_{3}(\overline{G}))
\end{align}}\normalsize
where $T_{3}(\overline{G})$ is the number of triangles in
$\overline{G}$. From equation~(\ref{theorem2}), we have
\small{\begin{align}\label{eff_g_dash} u(\overline{G}) & \le
\delta^{2} \left(2\left( \bigg\lfloor \frac{n^2}{4} \bigg\rfloor
+x\right)\right) - \frac{\delta^{2}}{(n-2)} \left(6 n
\left(\frac{4e-n^2}{9}\right) \right)
\end{align}}\normalsize
Since $T_3(G_{Turan}) = 0$, the efficiency of the Turan graph is:
\vspace{-0.07in} \small{\begin{align} u(G_{Turan}) = \sum_{i}
u_{i}(G_{Turan}) &=\delta^{2} \left(2\times \bigg\lfloor
\frac{n^2}{4} \bigg\rfloor \right) \vspace{-0.05in}
\end{align}}\normalsize

The change in efficiency ($\Delta{u}$) between the two graphs is
\vspace{-0.07in}
\begin{equation}
\label{deltagain}
\Delta{u} = u(\overline{G}) - u(G_{Turan}) \le 2 \delta^2 \left (x  - \frac{n}{(n-2)} \frac{4x}{3} \right)
\end{equation}
which is clearly negative for any $x>0$. This implies that the
Turan graph is the unique efficient graph.
\end{proof}
\vspace{-0.1in}
%\textit{Note:} In Equation~\ref{eqn5.5}, the inequality for $u(\overline{G})$ is strict as $d_i$ is replaced with (n-1) $\forall i$. This is possible only for a complete graph with sparsity $0$. Thus the $\Delta u$ in Equation~\ref{deltagain} is a strict inequality, and we also know if we reduce the number of edges we can achieve triangle free graphs but they too have a utility strictly less than the Turan graph. Thus we can conclude the Turan graph is the \textit{unique} graph with maximum utility (up to an isomorphism of the labels of the nodes).
% \subsection{Case: $ \delta < c $ and $ \delta^2 > (c - \delta) $}


\begin{lemma}
When $ \delta < c $ and $ \delta^2 > (c - \delta) $, the Turan
graph is the unique efficient graph.
\end{lemma}
\begin{proof}
We prove this by contradiction. Assume that $\overline{G}$ is any
graph other than the Turan graph and $\overline{G}$ is efficient.
We show below that $\overline{G}$ cannot have lesser number of edges than $G_{turan}$,

\begin{align}
\nonumber u(\overline{G}) &= \sum_{i=1}^{n} u_{i}(\overline{G}) =
(\delta-c)\sum_{i=1}^{n} d_i + \sum_{i=1}^{n} d_{i} \delta^{2} 
\left( 1 - \displaystyle\frac{\sigma_{i}}{\binom{d_{i}}{2}} \right)  \\
\nonumber & \le \left( \delta - c + \delta^2 \right)   \sum_{i=1}^{n} d_i \\
\nonumber & <  u(G_{turan}) \mbox{~whenever,~} \sum_{i=1}^{n} d_i < 2 \bigg\lfloor \frac{n^2}{4} \bigg\rfloor
\end{align}

And observe, if  $\overline{G}$ has same number of edges as
$G_{turan}$ and is different from it, it can contain triangles and
will have an utility less than that of $G_{turan}$, as the benefit
from bridging would go down and the benefit from direct links would
remain unchanged.  

Thus $\overline{G}$ contains more edges than $G_{turan}$. 
Observe, that the benefit from direct links is negative
$(\delta - c) \sum_{i=0}^{n} d_i < 0 $, and
$\overline{G}$ has an higher utility compared to that of $G_{turan}$. It has to be that the 
bridging benefits in $\overline{G}$ has to be greater than that of the
Turan graph, as the utility due to direct links term has become more
negative compared to its value in $G_{turan}$

\begin{align}
\nonumber u(\overline{G}) &= \sum_{i=1}^{n} u_{i}(\overline{G}) =
\underbrace{(\delta-c)\sum_{i=1}^{n} d_i}_{\text{negative}} +
\underbrace{\sum_{i=1}^{n} d_{i} \delta^{2} \left( 1 -
\displaystyle\frac{\sigma_{i}}{\binom{d_{i}}{2}} \right
)}_{\text{utility more than } G_{Turan}}
\end{align}

This implies that this graph would give a higher utility for the
$\delta = c$ case, as the first term is $0$ there. This
contradicts Theorem \ref{eff-thm-nrsuri} and so our assumption must be
wrong. Hence the Turan graph is efficient.
\end{proof}

% \newpage
% \subsection{ CASE: $ \delta > c $ and $\delta^2 > 3(\delta - c) $ }
\vspace{-0.15in}
\begin{table}[h]
\caption{{\textbf{Characterization of Topologies of Efficient
Networks in NFGL}}}\label{summarytable3} \vspace{0.1in} \centering
\begin {tabular} {||l||l||}
\hline
\hline
%&\\
{\textbf{Parameter Range}} & {\textbf{Efficient Topologies}} \\
%&\\
\hline
%&\\
$ \delta <  c $ and $\delta^2 < (c - \delta)$ & Null network \\
%&\\
\hline
%&\\
$ \delta < c $ and $ \delta^2 > (c - \delta) $  & Turan network \\
%&\\
\hline
$ \delta = c $ & Turan network \\
%&\\
\hline
$ \delta > c $ and $\delta^2 > 3(\delta - c) $ & Turan network \\
%&\\
%&\\
\hline
%&\\
$ \delta > c $ and $ (\delta - c ) > 2\delta^2$ & Complete network  \\
%&\\
%\hline
%                                         & Turan network \\
%$ \delta < c $ and $(c-\delta) = \delta^2$ & Null network \\
%&\\
\hline
\hline
\end {tabular}
\vspace{-0.2in}
\end{table}

\begin{lemma}
When $ \delta > c $ and $\delta^2 \geq 3(\delta - c) $, the Turan
graph is the unique efficient graph.
\end{lemma}
\begin{proof}
Let $\overline{G}$ be the efficient graph. Using a similar
analysis that lead to equation~(\ref{eff_g_dash}), we can see that
\small{
\begin{multline}\label{eff_g_dash1}
\vspace{-0.27in}
\nonumber u(\overline{G}) \le (\delta+c+\delta^{2}) \left(2\left(\displaystyle \bigg\lfloor \frac{n^2}{4} \bigg\rfloor +x\right)\right) - \frac{\delta^{2}}{(n-2)} \left(6 n \left( \frac{4e-n^2}{9}\right)\right) \\
= (\delta+c+\delta^{2}) \left(2 \left(\displaystyle \bigg\lfloor
\frac{n^2}{4} \bigg\rfloor +x\right)\right) -
\frac{\delta^{2}n}{(n-2)} \left(\frac{8x}{3}\right)
\vspace{-0.1in}
\end{multline}
} \normalsize{\noindent For the Turan graph, it can also be seen
by simple analysis that } \small{
\begin{align}
\vspace{-0.1in}
\nonumber u(G_{Turan}) &= \displaystyle 2\bigg\lfloor \frac{n^2}{4} \bigg\rfloor \left( \delta-c+\delta^2 \right) \\
\nonumber \Rightarrow u(\overline{G})-u(G_{Turan}) & \le 2x\left( (\delta-c+\delta^2) - \displaystyle \frac{4n\delta^2} {3(n-2)} \right) \\
 & < 2x\left( (\delta-c+ \delta^2) - \displaystyle \frac{4\delta^2}{3} \right)
 \vspace{-0.1in}
\end{align}
} \normalsize{\noindent Thus, when $\delta^2 \geq 3(\delta-c)$, the Turan graph is
    the unique efficient graph.}
% For sufficiently large $n$ such that $\displaystyle \frac{n}{n-2} \approx 1$, we can see that
% \begin{align}
% \end{align}
\end{proof}

% TO BE CHECKED WITH SUBBU
% This follows from the equation \ref{deltagain}. That equation can be
% made to go to a near zero only if the benefit from
% the direct links increases by  $ \frac{2}{3} x \delta^2 $.

% \subsection { $ \delta > c $ and $ (delta - c) < \delta^2 < 3(\delta - c) $ }

\vspace{-0.1in}
\begin{conjecture}\label{conj1}
When $ \delta > c $ and $ (\delta - c) \leq \delta^2 < 3(\delta -
c) $, the Turan graph is the efficient graph.
\end{conjecture}
\vspace{-0.15in}

\begin{lemma}
When $ \delta > c $ and $ (\delta - c ) > 2\delta^2$ , the
complete graph is the efficient graph.
\end{lemma}
\begin{proof}
It can be shown that starting with an arbitrary graph
$\overline{G}$ (which is not a complete graph), adding an edge
between two nodes $i$ and $j$ (with smallest degree) increases the
cumulative utility of these two nodes by at least $2\delta^2$. At
the same time, there is a decrease in utility of a \textit{common}
neighbour of nodes $i$ and $j$, say node $k$, as there is a
decrease in the bridging benefits of node $k$. It can be shown
that the cumulative decrease in utility of all such common
neighbours formed is $\displaystyle\frac{2\delta^2}{d_k-1} min
(d_i,d_j)$ which is less than equal to $2\delta^2$. Repeating the
above process, we get the complete network.
\end{proof}

\vspace{-0.3cm}
\begin{conjecture}\label{conj2}
When $ \delta > c $ and $ (\delta - c) \le 2\delta^2 $:

    (i) if $(\delta - c) > \frac{n}{n-2} \delta^2$, then the complete graph is the efficient
    graph.

    (ii) if $(\delta - c) < \frac{n}{n-2} \delta^2$, then the Turan graph is the efficient
    graph.
\end{conjecture}
\vspace{-0.1cm}

We summarize the above results on efficiency in
Table~\ref{summarytable3}.

%\textbf{Remark: } It can be shown (through some algebraic simplification) that the completely connected k-partite graph is less efficient than the EBCG. But, since this does not show that the EBCG is the efficient graph, we are not including the detailed proof here.
% \textbf{<TODO: We can show the above  result for any completely connected k-partite graph. ???>}


\vspace{-0.1cm}
\section{Price of Stability \textbf{\large{(P}}\small{\textbf{o}}\normalsize\textbf{\large{S)}} }\label{POS}
By invoking the results derived in the previous sections, we now
present our results on PoS (refer to Section \ref{results} for the
definition of PoS) for the proposed model.

\vspace{-0.2cm}
\begin{theorem}\label{pos-thm1} PoS is $1$ in each of the following
scenarios:
\noindent(i) $ \delta > c $ and $ (\delta - c ) > 2\delta^2$ \\
(ii) $ \delta > c $, $\delta^2 > (\delta - c) $ and $\delta^2 \geq 3(\delta - c) $ \\
(iii)$ \delta = c $ \\
(iv) $ \delta < c $ and $ \delta^2 > (c - \delta) $
\end{theorem}

This theorem can be proved easily using the results summarized
in Table~\ref{summarytable2} and Table~\ref{summarytable3}.

\noindent {\em Note: Since the null network is the only efficient network
when $\delta < c $ and $\delta^2 < (c - \delta)$, PoS is not
defined in this region.}

In view of Conjecture~\ref{conj1}, the following result presents
bounds on PoS.

% \vspace{-0.25cm}
\normalsize
\begin{theorem}
\label{pos-thm2} When $ \delta > c $ and $ (\delta - c) \leq
\delta^2 < 3(\delta - c) $, PoS $ > \frac{1}{2}$.
\end{theorem}
\begin{proof}
We know that, under the conditions $ \delta > c $ and $ (\delta - c) <\delta^2 < 3(\delta - c) $, the pairwise stable graph with the highest utility is the Turan graph (as seen from Table~\ref{summarytable2}).
%or the complete graph. If  Conjecture~\ref{conj1} is true, then the Turan graph is the efficient as well as the best pairwise stable network. Hence, $PoS = 1 > \frac{1}{2}$.
Let Conjecture~\ref{conj1} be false.
% Now, the best pairwise stable graph can be either the Turan graph or the complete graph.
In this scenario, let us denote the efficient graph by
$\overline{G}$. We will now evaluate an upper bound on the maximum
efficiency of $\overline{G}$. $\overline{G}$ has to have more
direct links than the Turan graph (as $\delta > c $) to be a
candidate for efficient graph. Let $\overline{G}$ have
$\left(\displaystyle \bigg\lfloor \frac{n^2}{4} \bigg\rfloor +
x\right)$ edges where $x>0$. \vspace{-0.1in} \small{
\begin{align}\label{efficiency_equation2}
\nonumber u(\overline{G}) = \sum_{i=1}^{n} u_{i}(\overline{G}) = (\delta-c)\sum_{i=1}^{n} d_i+ \sum_{i=1}^{n} d_{i} \delta^{2} \left( 1 - \displaystyle\frac{\sigma_{i}}{\binom{d_{i}}{2}} \right ) \\
\nonumber = (\delta-c+\delta^{2})\sum_{i=1}^{n} d_i - \delta^{2}\left(\displaystyle\frac{2\sigma_{i}}{d_i-1} \right )
\end{align}
} \normalsize Since  $d_i$ can be at most $(n-1)$, \small{
\begin{align}
\vspace{-0.1in}
\nonumber u(\overline{G}) \leq (\delta-c+\delta^{2}) n(n-1) - \left(\frac{2\delta^{2}}{n-2}\right) \sum_{i=1}^{n}  \sigma_i \\
\nonumber u(\overline{G}) \leq (\delta-c+\delta^{2}) n(n-1) -
\left(\frac{2\delta^{2}}{n-2}\right) T_3(\overline{G})
\vspace{-0.1in}
\end{align}
} \normalsize By equation~(\ref{theorem2}), we have \small{
\begin{align}
\vspace{-0.1in}
\nonumber u(\overline{G}) &\leq  (\delta-c+\delta^{2}) n(n-1) - \left(\frac{2\delta^{2}}{n-2}\right) \left(\displaystyle \frac {n(4e-n^2)}{9}\right) \\
\nonumber &= (\delta-c+\delta^{2}) n(n-1) -
\left(\frac{\delta^{2}n}{n-2}\right) \left(\displaystyle \frac
{8x}{9}\right) \vspace{-0.1in}
\end{align}
} \normalsize Since
$\displaystyle\left(\frac{\delta^{2}n}{n-2}\right)
\left(\displaystyle \frac {8x}{9}\right) > 0$, we have \small{
\begin{align}
\nonumber u(\overline{G}) \leq  (\delta-c+\delta^{2}) n(n-1)
\end{align}
} \normalsize
% If the Turan graph is the best pairwise stable graph, then we have
The Turan graph is pairwise stable under these conditions (refer
Table~\ref{summarytable2}), and $ u(G_{Turan}) =
(\delta-c+\delta^2) \left(\displaystyle 2 \bigg\lfloor
\frac{n^2}{4} \bigg\rfloor \right) $ \small{
\begin{align}
\nonumber PoS & \ge \frac{u(G_{Turan})}{u(\overline{G})} \geq
\displaystyle \frac{(\delta-c+\delta^2)
\left(\displaystyle\frac{n^2 - 1}{2}\right)}{(\delta-c+\delta^{2})
n(n-1) } = \displaystyle \frac{1}{2} + \frac{1}{2n} 
\end{align}
} \normalsize This implies that $ PoS > \frac{1}{2}$.
\end{proof}
\textit{Remark:} In view of Conjecture~\ref{conj2}, it can be
noted that a similar bound can be obtained in the region
\text{$\delta
> c$ and $(\delta-c) \le 2\delta^2$}. The details are not provided
here due to space constraints.

From Theorem \ref{pos-thm1} and Theorem \ref{pos-thm2} along with the empirical results, we conclude that, under mild conditions, the proposed NFGL produces efficient networks that are pairwise stable. This is desirable from the view of
system design.

%\begin{align}\label{eqn1}

%%%%%%%%%%%%%%%%%%%%nrsuri commented
%\begin{center}
%\begin{table}
%\label{eqn1}
%\begin{tabular}{l l}
%$\nonumber u(G_{Turan})$ & $= (\delta-c+\delta^2) \left(\displaystyle\frac{n^2}{2}\right)$ \\
%$\nonumber \Rightarrow PoS$ &= $\displaystyle \frac{u(G_{Turan})}{u(\overline{G})}$ \\
%$\nonumber \Rightarrow PoS$ & $\geq \displaystyle \frac{(\delta-c+\delta^2) \left(\displaystyle\frac{n^2}{2}\right)}{(\delta-c+\delta^{2}) n(n-1) } $\\
%$\nonumber \Rightarrow PoS $ & $\geq \displaystyle \frac{n}{2(n-1)} $\\
%$\Rightarrow PoS$ & $> \displaystyle \frac{1}{2}$
%\end{tabular}
%\end{table}
%\end{center}
%%%%%%%%%%%%%%%%%%%%nrsuri commented

%\end{align}

% If the complete graph is the best pairwise stable graph, then
% \begin{align}\label{eqn2}
% \nonumber u(G_{complete}) &= (\delta-c) n (n-1)\\
% \nonumber \Rightarrow PoS &= \displaystyle \frac{u(G_{complete})}{u(\overline{G})} \\
% \nonumber \Rightarrow PoS &\geq \displaystyle \frac{(\delta-c) \left(n(n-1)\right)}{(\delta-c+\delta^{2}) n(n-1) } \\
% \nonumber \Rightarrow PoS &\geq \displaystyle \frac{1}{1+\left(\frac{\delta^2}{(\delta-c)}\right)}
% \end{align}
% From hypothesis, we know that $1 < \frac{\delta^2}{\delta-c}< 3$
% \begin{align}
% \Rightarrow PoS &>\displaystyle\frac{1}{4}
% \end{align}
%
% From Equation~\ref{eqn1} and Equation~\ref{eqn2}, we have
% \begin{align}
% \Rightarrow PoS &> \displaystyle\frac{1}{4}
% \end{align}

\section{Conclusions and Future Work}\label{conclusion}
In this paper, we proposed a network formation game with local
information (NFGL) and studied topologies of pairwise stable and
efficient networks. Based on this analysis, we studied the
tradeoffs between pairwise stability and efficiency. In
particular, we computed the PoS of the proposed NFGL. Except for a
few configurations of $\delta$ and $c$, we have shown that PoS is
$1$. This means that, under mild conditions, that NFGL produces
efficient networks that are pairwise stable.

Here are a few pointers for future work. First, the framework
in this paper can be extended to the case of directed graphs and
weighed graphs. This involves certain challenges such as
defining utility model appropriately. Second, the setting in this
paper can extended by varying the notions of stability and
efficiency. We note that there are several possible notions of
stability and efficiency that exist in the literature. The choice
of an appropriate notion of stability as well as efficiency is a
topic of debate.

% \section*{ACKNOWLEDGEMENTS}
% We thank Gregoire Seux who was involved in some very useful discussions during the initial stages of this paper.

% \begin{justify}

% \bibitem{aumann:88}
% R.J. Aumann and R.B. Myerson.
% \newblock {\em Endogenous Formation of Links Between
% Players and Coalitions: An Application of the Shapley Value}.
% \newblock In: A.E. Roth (editor). The Shapley Value,
% Cambridge University Press, pages 175-191, 1988.

% \bibitem{bala:00}
% V.~Bala and S.~Goyal. \newblock {\em A Non-Cooperative Model of
% Network Formation}. \newblock Econometrica, 68, 2000.

\begin{small}
\begin{thebibliography}{9}
\vspace{0.2cm}

\bibitem{arcaute:08}
E. Arcaute, R. Johari, and S. Mannor. \newblock {\em Local
Two-Stage Myopic Dynamics for Network Formation Games}. \newblock
In Workshop on Internet and Network Economics (WINE), 2008.

\bibitem{anshelevich:03}
E.~Anshelevich, A.~Dasgupta, E.~Tardos, and T.~Wexler. \newblock
{\em Near-Optimal Network Design with Selfish Agents}.
\newblock In ACM STOC, 2003.

\bibitem{anshelevich:08}
E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler,
and T. Roughgarden. \newblock {\em The Price of Stability for
Network Design with Fair Cost Allocation}. \newblock SIAM Journal
on Computing, 38(4):1602-1623, 2008.

\bibitem{burt:07}
R.S. Burt. \newblock {\em Second-hand brokerage: Evidence on the
importance of local structure for managers, bankers, and
analysts}. Academy of Management Journal 50:119-148, 2007.

\bibitem{buskens-vanderijt:07}
V.~Buskens and A.~van~de Rijt.
\newblock Dynamics of networks if everyone strives for structural holes.
\newblock {\em American Journal of Sociology}, 114(2), 2008.

\bibitem{corbo:05}
J.~Corbo and D. Parkes.
\newblock {\em The Price of Selfish Behavior in Bilateral Network
Formation}.
\newblock In ACM PODC, 2005.

\bibitem{doreian06}
P. Doreian.
\newblock Actor network utilities and network evolution.
\newblock {\em Social Networks}, 28:137--164, 2006.

\bibitem{fabrikant:03}
A.~Fabrikant, A.~Luthra, E.~Maneva, C.~Papadamitriou, and
S.~Shenker. \newblock {\em On a Network Creation Game}. \newblock
In ACM PODC, 2003.

\bibitem{galeotti:06}
A.~Galeotti, S.~Goyal, J.~Kamphorst.
\newblock {\em Network formation with heterogeneous players}.
\newblock {\em Games and Economic Behavior}, 54(2):353-372, 2006.

\bibitem{goyal:07}
S.~Goyal.
\newblock {\em Connections: An Introduction to the Economics of Networks}.
\newblock Princeton University Press, Princeton and Oxford, 2007.

\bibitem{goyal-vegaredondo:07}
S.~Goyal and F.~Vega-Redondo.
\newblock Structural holes in social networks.
\newblock {\em Journal of Economic Theory}, 137(1):460--492, 2007.

%\bibitem{haller:03}
%H. Haller and S. Sarangi. \newblock {\em Nash Networks with
%Heterogeneous Agents}. \newblock LSU Working Paper 2003-06, 2003.

\bibitem{hummon00}
N.P. Hummon.
\newblock Utility and dynamic social networks.
\newblock {\em Social Networks}, 22:221-249, 2000.

\bibitem{jackson-wolinsky:96}
M.~O. Jackson and A.~Wolinsky.
\newblock A strategic model of social and economic networks.
\newblock {\em Journal of Economic Theory}, 71(1):44-74, 1996.

\bibitem{jackson:02}
M.~O. Jackson and A.~Watts.
\newblock The Evolution of Social and Economic Networks.
\newblock {\em Journal of Economic Theory}, 106(2):265-295, 2002.

%\bibitem{jackson:04}
%M.O. Jackson.
%\newblock {\em A Survey of Models of Network Formation: Stability and Efficiency}.
%\newblock In G. Demange and M. Wooders (eds.). Group Formation in Economics; Networks, Clubs and Coalitions. Cambridge University Press, U.K., 2004.

\bibitem{jackson:08}
M.~O. Jackson.
\newblock {\em Social and Economic Networks}.
\newblock Princeton University Press, Princeton and Oxford, 2008.

%\bibitem{johnson:00}
%C.~Johnson and R.P.~Gilles.
%\newblock {\em Spatial social networks}.
%\newblock {\em Review of Economic Design}, 5(3):273-299, 2000.

\bibitem{kstw:08}
J.~Kleinberg, S.~Suri, E.~Tardos, and T.~Wexler. Strategic network
formation with structural holes. In ACM EC, 2008.

%\bibitem{lopez:04}
%D. Lopez-Pintado. \newblock {\em A cost-sharing model of network
%formation: Anti-coordination games}. \newblock International
%Journal of Game Theory, 33(1):1-19, 2004.

%\bibitem{melendez:02}
%M.A. Melendez-Jimenez. \newblock {\em Network Formation and
%Coordination: Bargaining the Division of Link Costs}.
%\newblock In Proceedings of the 5th Spanish Meeting on Game Theory and
%Applications, 2002.

\bibitem{leonardi:07}
S. Leonardi and P. Sankowski.
\newblock {\em Network formation games with local coalitions}.
\newblock In ACM PODC, 2007.

\bibitem{myerson:91}
R.B. Myerson.
\newblock {\em Game Theory: Analysis of Conflict}.
\newblock Harvard University Press, Cambridge, USA, 1991.

\bibitem{nor:ste}
E.A. Nordhaus and B.M. Stewart. \newblock {\em Triangles in
Ordinary Graph}. \newblock Canadian Journal of Mathematics,
15(1):33-41, 1963.

\bibitem{turan}
P. Turan. {\em On an extremal problem in graph theory}. Matematikai es Fizikai Lapok, 1941

%\bibitem{sarangi:03}
%S. Sarangi, R. Kannan, and L. Ray. \newblock {\em The Structure of
%Information Networks}. \newblock Royal Economic Society Annual
%Conference, 2003.

% ADDED ROHITH
%\bibitem{jackson:2003}
%M.O. Jackson. {\em A Survey of Models of Network Formation: Stability and Efficiency}.
%Technical Report, CalTech, USA, 2003.

\end{thebibliography}
\end{small}

\end{document}
